﻿#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>
#include<assert.h>
#include<string.h>
#include<stdlib.h>

//打印100以内3倍数
//int main()
//{
//	int i = 1;
//	for (i = 1; i <= 100; i ++)
//	{
//		if (i % 3 == 0)
//		{
//			printf("%d ", i);
//		}
//	}
//	return 0;
//}

//
////把三个整数从大到小排
//int main()
//{
//	int i = 0;
//	int arr[3] = {2,1,3};
//	printf("交换前：\n");
//	for (i = 0; i < 3; i++)                                       
//	{
//		printf("%d ", arr[i]);
//	}
//	printf("交换后：\n");
//	//arr[0]最大
//	if (arr[0] > arr[1] && arr[0] > arr[2])
//	{
//		printf("%d ", arr[0]);
//		if (arr[1] < arr[2])
//		{
//			printf("%d ", arr[2]);
//			printf("%d ", arr[1]);
//		}
//		else
//		{
//			printf("%d ", arr[1]);
//			printf("%d ", arr[2]);
//		}
//	}
//	//arr[1]最大
//	else if (arr[1] > arr[0] && arr[1] > arr[2])
//	{
//		printf("%d ", arr[1]);
//		if (arr[0] < arr[2])
//		{
//			printf("%d ", arr[2]);
//			printf("%d ", arr[0]);
//		}
//		else
//		{
//			printf("%d ", arr[0]);
//			printf("%d ", arr[2]);
//		}
//	}
//	else
//	{
//		printf("%d ", arr[2]);
//		if (arr[0] < arr[1])
//		{
//			printf("%d ", arr[1]);
//			printf("%d ", arr[0]);
//		}
//		else
//		{
//			printf("%d ", arr[0]);
//			printf("%d ", arr[1]);
//		}
//	}
//	return 0;
//}


// 

////打印1000到2000之间的闰年
//int main()
//{
//	int i = 1;
//	for (i = 1000; i <= 2000; i++)
//	{
//		if (i % 4 == 0 && i % 100 != 0)
//		{
//			printf("%d ", i);
//		}
//		if (i % 400 == 0)
//		{
//			printf("%d ", i);
//		}
//	}
//	return 0;
//}


////打印两个数的最大公约数
//int main()
//{
//	int i = 1;
//	int a = 0, b = 0, z = 0, d = 0;
//	scanf("%d %d", &a, &b);
//	//判断ab哪个大，哪个小
//	if (a > b)
//	{
//		z = b;
//		d = a;
//	}
//	else
//	{
//		z = a;
//		d = b;
//	}
//	//i从小的开始
//	for (i = z; i > 1; i--)
//	{
//		//首先确认z可以被i整除
//		if (z%i == 0)
//		{
//			if (d % i == 0)
//			{
//				printf("最大公约数为：%d\n", i);
//				break;
//			}
//		}
//	}
//	return 0;
//}


////打印9*9乘法表
//int main()
//{
//	int a = 0;
//	int b = 0;
//	for (a = 1; a <= 9; a++)
//	{
//		for (b = 1; b <= a; b++)
//		{
//			printf("%d*%d=%-2d", b, a, a*b);
//		}
//		printf("\n");
//	}
//	return 0;
//}


////打印10个整数中的最大值
//int main()
//{
//	int arr[10] = {7,9,10,4,5,8,6,2,11,13};
//	int i = 0;
//	int tmp = 0;
//	for (i = 1; i <= 9; i++)
//	{
//		if (arr[0] < arr[i])
//		{
//			tmp = arr[0];
//			arr[0] = arr[i];
//			arr[i] = tmp;
//		}
//	}
//	printf("%d", arr[0]);
//	return 0;
//}


////求1/1-1/2+1/3-1/4+1/5.......+1/99-1/100
//int main()
//{
//	int i = 0;
//	float sum = 0.0;
//	for (i = 1; i <= 100; i++)
//	{
//		int a = 1;//控制正负
//		if (i % 2 == 0)
//		{
//			a=-1;
//		}
//		sum = sum + 1.0 / (a*i);
//	}
//	printf("%lf ", sum);
//	return 0;
//}


////a=8，a在b变之后改变
//int main()
//{
//	int a = 0, b = 0;
//	for (a = 1, b = 1; a <= 100; a++)
//	{
//		if (b >= 20) break;
//		if (b % 3 == 1)
//		{
//			b = b + 3;
//			continue;
//		}
//		b = b - 5;
//	}
//	printf("%d\n", a);
//	return 0;
//}


////找100内9的个数
//int main()
//{
//	int i = 0,count=0;
//	for (i = 100; i >0; i--)
//	{
//		//算个位
//		if (i % 10 != 0)//10%10=0；0%9=0会额外计算
//		{
//			if ((i % 10) % 9 == 0)
//			{
//				count++;
//			}
//		}
//		if (i / 10!=0)//10%10=0；0%9=0会额外计算
//		{
//			if ((i / 10) % 9 == 0)
//			{
//				count++;
//				continue;
//			}
//		}
//	}
//	printf("%d ",count);
//	return 0;
//}

////猜数字小游戏
//#include<stdlib.h>
//#include<time.h>
//void menu()
//{
//	printf("************************\n");
//	printf("****** 1、开始游戏 *****\n");
//	printf("****** 0、退出游戏 *****\n");
//	printf("************************\n");
//}
//void game()
//{
//	int s = 0;
//	s = rand() % 100 + 1;
//	int n = 0;
//	printf("请猜数字：（1~100）\n");
//	while (1)
//	{
//		
//		scanf("%d", &n);
//		if (n < s)
//		{
//			printf("猜小了\n");
//		}
//		else if (n > s)
//		{
//			printf("猜大了\n");
//
//		}
//		else
//		{
//			printf("猜对了\n");
//			break;
//		}
//	}
//
//}
//int main()
//{
//	int input = 0;
//	do
//	{
//		menu();
//		srand((unsigned int)time(NULL));
//		printf("是否游玩：\n");
//		scanf("%d", &input);
//		switch (input)
//		{
//		case 1:
//			game();
//			break;
//		case 2:
//			printf("退出游戏\n");
//			break;
//		default:
//			printf("输入错误，请重新输入\n");
//			break;
//		}
//	} while (input);
//	return 0;
//}


////二分查找
//int main()
//{
//	int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
//	int sz = sizeof(arr) / sizeof(arr[0]);
//	int i = 0;
//	printf("请输入要查找的数字:\n");
//	scanf("%d", &i);
//	int left = 0;
//	int right = sz - 1;
//	while (left<=right)//等号专门找7和4，下标左右两边相等
//	{
//		int mid = (left + right) / 2;
//		if (i < arr[mid])
//		{
//			right = mid - 1;
//		}
//		else if (i > arr[mid])
//		{
//			left = mid + 1;
//		}
//		else
//		{
//			printf("找到了，下标是：%d\n", mid);
//			break;
//		}
//	}
//	if (left > right)
//	{
//		printf("没找到\n");
//	}
//	return 0;
//}


////在convert填何值，使最后打印结果为80000007
////80000007 转为2进制为
////1000 0000 0000 0000 0000 0000 0000 0111
////  | 有一个1则返回1；& 两个都为1返回1；^ 相同为0相异为1
//#include <stdio.h>
//////第一种
////int convert(int i) {
////	return i |= 1 << 31;
////}
////第二种
//int convert(int i) {
//	return i ^= 1 << 31;
//}
//int main() {
//	int value = 7;
//	printf("%x\n", convert(value));
//	return 0;
//}




//7月21号作业

////打印乘法口诀表，用函数，想输入几就打印几行
//void chengfa(int a)
//{
//	int i = 0;
//	for (i = 1; i <= a; i++)
//	{
//		int j = 1;
//		for (j = 1; j <= i; j++)
//		{
//			printf("%-2d*%-2d=%-2d ", i, j, i*j);
//		}
//		printf("\n");
//	}
//}
//int main()
//{
//	int a = 0;
//	scanf("%d", &a);
//	chengfa(a);
//	return 0;
//}
//
//
////函数实现交换两个整数的内容
//void swap(int* a1,int *b1)
//{
//	int tmp = *a1;
//	*a1 = *b1;
//	*b1 = tmp;
//}
//int main()
//{
//	int a = 10, b = 20;
//	printf("交换前a=%d ,b=%d \n", a, b);
//	swap(&a, &b);
//	printf("交换后a=%d ,b=%d \n", a, b);
//	return 0;
//}
//
//
////用函数判断是否为闰年
//int Isrun(int year)
//{
//	if (((year % 4) == 0 && (year % 100 != 0)) || (year % 400 == 0))
//	{
//		return 1;
//	}
//	else
//	{
//		return 0;
//	}
//}
//int main()
//{
//	int year = 0;
//	printf("请输入年份：");
//	while (scanf("%d", &year) != EOF)
//	{
//		if(Isrun(year))
//		{ 
//			printf("%d是闰年。\n", year);
//		}
//		else
//		{
//			printf("%d是不是闰年。\n", year);
//		}
//		getchar();
//		printf("请继续输入年份：");
//	}
//
//	return 0;
//}

//#include<math.h>
////用函数打印一个范围内的所由素数
//void Is_prime(int a, int b)
//{
//	int i = 0;
//	int count = 0;
//	if (a % 2 == 0)//判断是否从偶数开始
//	{
//		for (i = a + 1; i <= b; i += 2)
//		{
//			int j = 1;
//			for (j = 2; j <= sqrt(i); j++)
//			{
//				if (i % j == 0)
//				{
//					break;
//				}
//			}
//			//判断上面循环是否走完了
//			if (j > sqrt(i))
//			{
//				printf("%d ", i);
//				count++;
//			}
//		}
//	}
//	else
//	{
//		for (i = a; i <= b; i+=2)
//		{
//			int j = 1;
//			for (j = 2; j <= sqrt(i); j++)
//			{
//				if (i % j == 0)
//				{
//					break;
//				}
//			}
//			//判断上面循环是否走完了
//			if (j > sqrt(i))
//			{
//				printf("%d ", i);
//				count++;
//			}
//		}
//	}
//
//	printf("素数个数为：%d\n", count);
//}
//int main()
//{
//	int a = 0,b=0;
//	printf("请输入范围(先小后大)： ");
//	scanf("%d %d", &a, &b);
//	Is_prime(a,b);
//	return 0;
//}




////7月23号作业
//int Fun(int n)
//{
//	if (n == 5)
//		return 2;
//	else
//		return 2 * Fun(n + 1);
//}
//int main()
//{
//	int a=Fun(2);
//	printf("%d", a);
//	return 0;
//}

////递归和非递归实现斐波那契数列
////1 1 2 3 5 8 13 21 34 55
////递归实现
//int D_Fei(int n)//5
//{
//	if (n <= 2)
//		return 1;
//	else
//	{
//		return D_Fei(n - 2) + D_Fei(n - 1);
//	}
//}
////非递归实现
//int F_Fei(int n)
//{
//	int i = 1;//控制循环
//	int a = 1;
//	int b = 1;
//	int c = 1;
//	if (n <= 2)
//		return c;
//	else
//	{
//		for (i = 3; i <= n; i++)
//		{
//			c = a + b;
//			a = b;
//			b = c;
//		}
//		return c;
//	}
//}
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//
//	//int a=D_Fei(n);
//	int a = F_Fei(n);
//	printf("%d ", a);
//	return 0;
//}


////递归实现n的k次方
//int CiFang(int n, int k)
//{
//	if (k == 0)
//		return 1;
//	else
//		return n*CiFang(n, k - 1);
//}
//int main()
//{
//	int n = 0;
//	printf("请输入数字：\n");
//	scanf("%d", &n);
//	getchar();
//	int k = 0;
//	printf("请输入次方：\n");
//	scanf("%d", &k);
//	int sum=CiFang(n, k);
//	printf("%d的%d次方为%d", n, k, sum);
//	return 0;
//}


////写一个递归函数DigitSum(n)，输入一个非负整数，返回组成它的数字之和
//int Add(int n)
//{
//	//用于累加,注意：一定要加上srtatic，要不然递归回归时，i都会返回到0重新加，做不到累加的效果
//	static int i = 0;
//	if (n > 9)
//	{
//		Add(n / 10);
//		return i += n % 10;
//	}
//	else
//	{
//		return i+=n;
//	}
//}
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	int sum = Add(n);
//	printf("%d", sum);
//}


//////编写一个函数 reverse_string(char * string)（递归实现）
//char reverse_string(char *string,int sz)
//{
//	int left = 0;
//	int right = sz;
//	while (left <= right)
//	{
//		char tmp = 0;
//		tmp = string[left];
//		string[left] = string[right];
//		string[right] = tmp;
//		//sz-2的目的，是让右边的下标向左移动一个，指向d
//		//若是sz-1，由于起始位置+1了，那么指向的位置其实还是原先f的位置（f被替换成a了）
//		return reverse_string(string + 1, sz -2);
//	}
//}
//int main()
//{
//	char arr[] = "abcedfg";
//	int sz = sizeof(arr) / sizeof(arr[0]);
//	printf("翻转前：%s\n", arr);
//	//sz-2目的是使sz直接对着f的下标
//	reverse_string(arr,sz-2);
//	printf("翻转后：%s\n", arr);
//	return 0;
//}


////用递归和非递归实现strlen效果
////非递归
//size_t My_strlen1(char arr[],int sz)
//{
//	int i = 0;
//	int sum = 0;
//	for (i = 0; i < sz; i++)
//	{
//		if (arr[i] != '\0')
//		{
//			sum++;
//		}
//		else
//			return sum;
//	}
//}
////递归
//size_t My_strlen2(char arr[])
//{
//	if (arr[0] != '\0')
//	{
//		return 1 + My_strlen2(arr + 1);
//	}
//	else
//		return 0;
//}
//int main()
//{
//	char arr[] = "abcdef";
//	int sz = sizeof(arr) / sizeof(arr[0]);
//	//int a=My_strlen1(arr,sz);//非递归
//	int a = My_strlen2(arr);//递归
//	printf("%d", a);
//	return 0;
//}


////递归和非递归分别实现求n的阶乘（不考虑溢出的问题）
////递归
//int D_Jie(int n)
//{
//	if (n >= 1)
//	{
//		return n*D_Jie(n - 1);
//	}
//	else
//	{
//		return 1;
//	}
//}
////非递归
//int F_Jie(int n)
//{
//	int i = 1;
//	int sum = 1;
//	for (i = 1; i <= n; i++)
//	{
//		sum =sum*i;
//	}
//	return sum;
//}
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	//int a=D_Jie(n);
//	int a = F_Jie(n);
//	printf("%d", a);
//	return 0;
//}


////递归方式实现打印一个整数的每一位
//void print(int n)
//{
//	if (n > 9)
//	{
//		print(n / 10);
//		printf("%d ", n % 10);
//	}
//	else
//	{
//		printf("%d ", n);
//	}
//}
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	print(n);
//	return 0;
//}


//////汉诺塔问题
//void swap(char a, char b, char c)
//{
//	printf("%c->%c\n", a, b);
//	printf("%c->%c\n", a, c);
//	printf("%c->%c\n", b, c);
//}
//// HanNuoTa(起始位置，中转位置，目的位置)
//void HanNuoTa(char a, char b, char c, int n)
//{
//	if (n >= 3)
//	{
//		HanNuoTa(a, c, b, n - 1);
//		printf("%c->%c\n", a, c);
//		HanNuoTa(b, a, c,n - 1);
//	}
//	else
//	{
//		swap(a, b, c);
//	}
//}
//int main()
//{
//	int n = 4;//盘子数量
//	char a = 'A', b = 'B', c = 'C';//ABC代表三个柱子
//	HanNuoTa(a, b, c, n);
//	return 0;
//}




////7月24号课后作业
////创建一个整形数组，完成对数组的操作
////实现函数init() 初始化数组为全0
////实现print()  打印数组的每个元素
////实现reverse()  函数完成数组元素的逆置。
//void init(int arr[10])
//{
//	int i = 0;
//	for (i = 0; i < 10; i++)
//	{
//		arr[i] = 0;
//	}
//}
//void print(int arr[10])
//{
//	int i = 0;
//	for (i = 0; i < 10; i++)
//	{
//		printf("%d ",arr[i]);
//	}
//}
//void reverse(int arr[10])
//{
//	int i = 0;
//	for (i = 0; i < 10; i++)
//	{
//		int j = 0;
//		for (j = 9; j > 0; j--)
//		{
//			int tmp = arr[i];
//			arr[i] = arr[j];
//			arr[j] = tmp;
//		}
//	}
//}
//int main()
//{
//	int arr[10];
//	init(arr);
//	print(arr);
//	reverse(arr);
//	return 0;
//}


////对整形数组进行冒泡排序
//void mao(int arr[10], int sz)
//{
//	int i = 0;
//	//约束跑几次
//	for (i = 0; i < sz-1; i++)
//	{
//		int j = 0;
//		//怎么进行交换
//		for (j = 0; j < sz-1-i; j++)
//		{
//			if (arr[j]>arr[j+1])
//			{
//				int tmp = arr[j];
//				arr[j] = arr[j+1];
//				arr[j+1] = tmp;
//			}
//		}
//	}
//}
//int main()
//{
//	int arr[10] = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
//	int sz = sizeof(arr) / sizeof(arr[0]);
//	int k = 0;
//	printf("排序前：");
//	for(k = 0; k < sz; k++)
//	{
//		printf("%d ",arr[k]);
//	}
//	mao(arr, sz);
//	printf("排序后：");
//	for (k = 0; k < sz; k++)
//	{
//		printf("%d ", arr[k]);
//	}
//	return 0;
//}


////三子棋小游戏
//#include"game_3ziqi.h"
////菜单
//void mune()
//{
//	printf("*************************\n");
//	printf("*******  1.play  ********\n");
//	printf("*******  0.exit  ********\n");
//	printf("*************************\n");
//}
//void game()
//{
//	char arr[ROW][COL] = {0};
//	ChuShi(arr, ROW, COL);
//	PrintArr(arr, ROW, COL);
//	char ret = 'j';//判断游戏是否继续的条件
//	while (1)
//	{
//		PlayerMove(arr, ROW, COL);
//		PrintArr(arr, ROW, COL);
//		ret = IsWin(arr, ROW, COL);
//		if (ret != 'j')
//		{
//			break;
//		}
//		ComputerMove(arr, ROW, COL);
//		PrintArr(arr, ROW, COL);
//		ret=IsWin(arr, ROW, COL);
//		if (ret != 'j')
//		{
//			break;
//		}
//	}
//	if (ret == '*')
//	{
//		printf("玩家胜利\n");
//	}
//	if (ret == '#')
//	{
//		printf("电脑胜利\n");
//	}
//	if (ret == 'p')
//	{
//		printf("平局\n");
//	}
//}
//int main()
//{
//	int input = 0;
//	srand((unsigned int)time(NULL));
//	do
//	{
//		mune();
//		printf("是否游玩(0/1)？\n");
//		scanf("%d", &input);
//		switch (input)
//		{
//		case 1:
//			game();
//			break;
//		case 0:
//			printf("退出游戏\n");
//		default:
//			printf("输入错误，请重新输入！\n");
//		}
//	} while (input);
//	return 0;
//}


//int main()
//{
//	int n = -1;
//	printf("%d", n << 1);
//	printf("%d", n >> 1);
//}




////7月27号作业

//求打印的值
//#include <stdio.h>
//int main()
//{
//	int a, b, c;
//	a = 5;
//	c = ++a;
//	b = ++c, c++, ++a, a++;
//	b += a++ + c;
//	printf("a = %d b = %d c = %d\n:", a, b, c);
//	return 0;
//}

//不允许创建临时变量，交换两个整数的内容
//int main()
//{
//	int a = 3;
//	int b = 5;
//	printf("交换前,a=%d,b=%d\n", a, b);
//
//	////方法1（可能会溢出）
//	//a = a + b;
//	//b = a - b;
//	//a = a - b;
//
//	//方法2，使用^异或
//	//^异或特点：a^a=0;		a^0=a;
//	a = a^b;
//	b = a^b;//b = a^b^b = a^0 = a
//	a = a^b;//a = a^b^a = b^0 = b 
//
//	printf("交换后,a=%d,b=%d\n", a, b);
//	return 0;
//}

////查询一个数字的二进制中1的个数
//int NumberOf1(int n) {
//	// write code here
//	int count = 0;
//	int j = 0;
//	int x = 0;
//	for (j = 0; j<32; j++)
//	{
//		x = n >> j;
//		if ((x & 1) == 1)
//		{
//			count++;
//		}
//	}
//	return count;
//}
//int main()
//{
//	int n = 10;
//	int count = NumberOf1(n);
//	printf("%d", count);
//	return 0;
//}

////获取一个整数二进制序列中所有的偶数位和奇数位，分别打印出二进制序列
//int main()
//{
//	int n = 11;
//	//00000000000000000000000000001011
//	int i = 0;
//	int Ou_count = 0;
//	int Ji_count = 0;
//
//	//奇数位
//	for (i = 0; i < 32; i += 2)
//	{
//		int x = n >> i;
//		if ((x & 1) == 1)
//		{
//			Ji_count++;
//		}
//	}
//	//偶数位
//	for (i = 1; i < 32; i += 2)
//	{
//		int x = n >> i;
//		if ((x & 1) == 1)
//		{
//			Ou_count++;
//		}
//	}
//	printf("奇数位有%d个\n", Ji_count);
//	printf("偶数位有%d个\n", Ou_count);
//	return 0;
//}
//
////编程实现：两个int（32位）整数m和n的二进制表达中，有多少个位(bit)不同？ 
//int main()
//{
//	int m = 1999;
//	int n = 2299;
//	int i = 0;
//	int x = m^n;
//	int count = 0;
//
//	for (i = 0; i < 32; i++)
//	{
//		int y = x >> i;
//		if ((y & 1) == 1)
//		{
//			count++;
//		}
//	}
//	printf("%d\n", count);//7
//	return 0;
//}




//7月28号作业

////输入两个升序排列的序列，将两个序列合并为一个有序序列并输出。
////第一行包含两个正整数n, m，用空格分隔。n表示第二行第一个升序序列中数字的个数，m表示第三行第二个升序序列中数字的个数。
////第二行包含n个整数，用空格分隔。	0<n,m<1000
////第三行包含m个整数，用空格分隔。
//int main() {
//	int n = 0, m = 0;
//	int nrr[1000] = { 0 };//存放n
//	int mrr[1000] = { 0 };//存放m
//	int sum[2000] = { 0 };//存放n和m
//	int i = 0;
//	scanf("%d %d", &n, &m);
//	getchar();
//	//把输入的数据存到nrr中
//	for (i = 0; i<n; i++)
//	{
//		int tmp = 0;
//		scanf("%d", &tmp);
//		getchar();
//		nrr[i] = tmp;
//	}
//
//	//把输入的数据存到mrr中
//	for (i = 0; i<m; i++)
//	{
//		int tmp = 0;
//		scanf("%d", &tmp);
//		getchar();
//		mrr[i] = tmp;
//	}
//
//	//先把nrr和mrr全存到sum中
//	for (i = 0; i<n; i++)
//	{
//		sum[i] = nrr[i];
//	}
//	int j = 0;//确保mrr数组要从0开始
//	for (i = n, j = 0; i < n + m && j < m; i++, j++)
//	{
//		sum[i] = mrr[j];
//	}
//
//	//对sum进行冒泡排序
//	for (i = 0; i<m + n; i++)
//	{
//		for (int j = i + 1; j<m + n; j++)
//		{
//			if (sum[j]<sum[i])
//			{
//				int tmp = sum[i];
//				sum[i] = sum[j];
//				sum[j] = tmp;
//			}
//		}
//	}
//
//	//打印结果
//	for (i = 0; i<m + n; i++)
//	{
//		printf("%d ", sum[i]);
//	}
//
//	return 0;
//}

////输入年份月份，输出当前月份的天数
//int main() {
//	int year = 0, month = 0;
//	while (scanf("%d %d", &year, &month) != EOF)
//	{
//		if (((year % 4 == 0) && (year % 100 != 0)) || (year % 400 == 0))
//		{
//			switch (month)
//			{
//			case 1:
//				printf("%d\n", 31);
//				break;
//			case 2:
//				printf("%d\n", 29);
//				break;
//			case 3:
//				printf("%d\n", 31);
//				break;
//			case 4:
//				printf("%d\n", 30);
//				break;
//			case 5:
//				printf("%d\n", 31);
//				break;
//			case 6:
//				printf("%d\n", 30);
//				break;
//			case 7:
//				printf("%d\n", 31);
//				break;
//			case 8:
//				printf("%d\n", 31);
//				break;
//			case 9:
//				printf("%d\n", 30);
//				break;
//			case 10:
//				printf("%d\n", 31);
//				break;
//			case 11:
//				printf("%d\n", 30);
//				break;
//			case 12:
//				printf("%d\n", 31);
//				break;
//			}
//		}
//		else
//		{
//			switch (month)
//			{
//			case 1:
//				printf("%d\n", 31);
//				break;
//			case 2:
//				printf("%d\n", 28);
//				break;
//			case 3:
//				printf("%d\n", 31);
//				break;
//			case 4:
//				printf("%d\n", 30);
//				break;
//			case 5:
//				printf("%d\n", 31);
//				break;
//			case 6:
//				printf("%d\n", 30);
//				break;
//			case 7:
//				printf("%d\n", 31);
//				break;
//			case 8:
//				printf("%d\n", 31);
//				break;
//			case 9:
//				printf("%d\n", 30);
//				break;
//			case 10:
//				printf("%d\n", 31);
//				break;
//			case 11:
//				printf("%d\n", 30);
//				break;
//			case 12:
//				printf("%d\n", 31);
//				break;
//			}
//		}
//	}
//	return 0;
//}

////变种水仙花数 - Lily Number：把任意的数字，从中间拆分成两个数字，比如1461 可以拆分成（1和461）, （14和61）, （146和1), 如果所有拆分后的乘积之和等于自身，则是一个Lily Number。
////例如：
////655 = 6 * 55 + 65 * 5
////1461 = 1 * 461 + 14 * 61 + 146 * 1
////求出 5位数中的所有 Lily Number。
//int main() {
//	int n = 0;
//	for (n = 9999; n<100000; n++)
//	{
//		//3位数
//		if (n<1000)
//		{
//			if (n == (((n / 100)*(n % 100) + (n / 10)*(n % 10))))
//			{
//				printf("%d ", n);
//			}
//		}
//
//		//4位数
//		else if (n<10000)
//		{
//			if (n == ((n / 1000)*(n % 1000) + (n / 100)*(n % 100) + (n / 10)*(n % 10)))
//			{
//				printf("%d ", n);
//
//			}
//		}
//
//		//5位数
//		else
//		{
//			if (n == ((n / 10000)*(n % 10000) + (n / 1000)*(n % 1000) + (n / 100)*(n % 100) + (n / 10)*(n % 10)))
//			{
//				printf("%d ", n);
//			}
//		}
//	}
//	return 0;
//}

//int i;//不初始化，默认是0
//int main()
//{
//	i--;
//	if (i > sizeof(i))
//	{
//		printf(">\n");
//	}
//	else
//	{
//		printf("<\n");
//	}
//	return 0;
//}




//7月29号作业

////写一个函数打印arr数组的内容，不使用数组下标，使用指针。
////arr是一个整形一维数组
//int main()
//{
//	int arr1[] = { 1, 2, 3, 4, 5 };
//	int arr2[] = { 2, 3, 4, 5, 6 };
//	int arr3[] = { 3, 4, 5, 6, 7 };
//
//	int *arr[] = { arr1, arr2, arr3 };
//	for (int i = 0; i < 3; i++)
//	{
//		for (int j = 0; j < 5; j++)
//		{
//			printf("%d ", (*(arr+i))[j]);
//		}
//		printf("\n");
//	}
//	return 0;
//}


//int main() {
//	char arr[] = "0";
//	//while ((scanf("%c", arr)) != '\n')
//	//{
//	//	;
//	//}
//	gets(arr);
//	//scanf("%s", arr);
//	int sz = strlen(arr);
//	int left = 0;
//	int right = sz - 1;
//	while (left < right)
//	{
//		char tmp = arr[left];
//		arr[left] = arr[right];
//		arr[right] = tmp;
//		left++;
//		right--;
//	}
//	printf("%s", arr);
//	return 0;
//}

//int main()
//{
//	int j = 0;
//	int k = 1;
//	for (int i = 1; i < 8; i++,k+=2)
//	{
//		for (j = 0; j < 7-i;j++ )
//		{
//			printf("%c", ' ');
//		}
//		int n = k;//确保k的值不变
//		while (n)
//		{
//			printf("%c", '*');
//			n--;
//		}
//		printf("\n");
//	}
//	//打印下面的
//	k = 13;
//	for (int i = 1; i < 8; i++, k -= 2)
//	{
//		for (j = 0; j < i-1 ; j++)
//		{
//			printf("%c", ' ');
//		}
//		int n = k;
//		while (n)
//		{
//			printf("%c", '*');
//			n--;
//		}
//		printf("\n");
//	}
//	return 0;
//}

////求出0～100000之间的所有“水仙花数”并输出。
////“水仙花数”是指一个n位数，其各位数字的n次方之和确好等于该数本身，如:153＝1 ^ 3＋5 ^ 3＋3 ^ 3，则153是一个“水仙花数”。
//int Li(int n)
//{
//	return n*n*n;
//}
//int Si(int n)
//{
//	return n*n*n*n;
//}
//int Wu(int n)
//{
//	return n*n*n*n*n;
//}
//int Liu(int n)
//{
//	return n*n*n*n*n*n;
//}
//int main()
//{
//	int n = 0;
//	for (n = 100; n <= 100000; n++)
//	{
//		//2位数
//		//if (n < 100)
//		//{
//		//	if (Li(n % 10) + Li(n / 10) == n)
//		//	{
//		//		printf("%d ", n);
//		//	}
//		//}
//		//3位数
//		if (n < 1000)
//		{
//			if (Li(n % 10) + Li((n / 10) % 10)+Li((n/100)%10) == n)
//			{
//				printf("%d ", n);
//			}
//		}
//		//4位数
//		else if (n < 10000)
//		{
//			if (Si(n % 10) + Si((n / 10) % 10) + Si((n / 100) % 10) + Si((n/1000)%10) == n)
//			{
//				printf("%d ", n);
//			}
//		}
//		//5位数
//		else if (n < 100000)
//		{
//			if (Wu(n % 10) + Wu((n / 10) % 10) + Wu((n / 100) % 10) + Wu((n / 1000) % 10)+Wu((n/10000)%10) == n)
//			{
//				printf("%d ", n);
//			}
//		}
//		//6位数
//		else
//		{
//			if (Liu(n % 10) + Liu((n / 10) % 10) + Liu((n / 100) % 10) + Liu((n / 1000) % 10) + Liu((n / 10000) % 10) + Liu(n / 100000) % 10 == n)
//			{
//				printf("%d ", n);
//			}
//		}
//	}
//	return 0;
//}

////求Sn = a + aa + aaa + aaaa + aaaaa的前5项之和，其中a是一个数字，
////例如：2 + 22 + 222 + 2222 + 22222
//long Sn(int n)
//{
//	return n + (n * 10 + n) + (n * 100 + n * 10 + n) + (n * 1000 + n * 100 + n * 10 + n) + (n * 10000 + n * 1000 + n * 100 + n * 10 + n);
//}
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	long ret = Sn(n);
//	printf("%ld", ret);
//	return 0;
//}

////数据在内存中是倒着存的，所以只改变了存到内存的第一个字节，第一个字节存放的是44，所以答案是11223300
//#include <stdio.h>
//int main()
//{
//	int a = 0x11223344;
//	char *pc = (char*)&a;
//	*pc = 0;
//	printf("%x\n", a);
//	return 0;
//}




////7月31号作业
//
////喝汽水，1瓶汽水1元，2个空瓶可以换一瓶汽水，给20元，可以多少汽水（编程实现）
//int main()
//{
//	int n = 20;//20元
//	int kong = 0;//空瓶数量
//	int count = 0;//统计喝多少汽水
//	while (n)
//	{
//		n--;
//		count++;
//		kong++;
//		if ( kong >= 2)
//		{
//			kong -= 2;
//			count++;
//			kong++;
//		}
//	}
//	printf("%d", count);
//	return 0;
//}

////VS开发环境调试下面的代码，画图解释下面代码的问题
//#include <stdio.h>
//int main()
//{
//	int i = 0;
//	int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
//	for (i = 0; i <= 12; i++)
//	{
//		arr[i] = 0;
//		printf("hello bit\n");
//	}
//	return 0;
//}
////上述代码我们粗略来看本来应该是一个数组越界访问的问题
////但是在Debug版本里，我们发现他会进入死循环
////是因为在vs进行栈区的使用时，是优先使用高地址，然后再用低地址的
////而数组随着下标的增长，地址是由低到高变化，即数组由低到高地址进行储存。
////那在我们访问的时候由于数组在上，i在下，再for循环不断的进行，i的值的增大，数组开始了越界访问
////由于vsDebug版本下，会把i放在arr数组下面第三个地址的位置，即&(arr[12])=&i;
////这时我们又改变了arr[12]的值，就相当于使i=0；这样就会进入一个死循环
////而release版本下，会把我们的i放在arr数组上面，就不会死循环，而是打印13个hello bit





////8月1号作业
//
////自己实现strlen
//#include <assert.h>
//size_t my_strlen(const char* arr)
//{
//	assert(arr != NULL);
//	size_t count = 0;
//	while (*arr != '\0')
//	{
//		count++;
//		arr++;
//	}
//	return count;
//}
//int main()
//{
//	char arr[] = "abcedf";
//	size_t ret = my_strlen(arr);
//	printf("%d", ret);
//	return 0;
//}
////
////输入一个整数数组，实现一个函数，
////来调整该数组中数字的顺序使得数组中所有的奇数位于数组的前半部分，
////所有偶数位于数组的后半部分。
////思路一：把原数组的奇数偶数都挑出来，然后再存回原数组中（消耗内存大）
////思路二：（双指针）原数组从前往后找偶数，从后往前找奇数，然后二者进行交换（直到二者指向一个元素时停止）（耗内存小）
//void swap(int arr[], int sz)
//{
//	//奇数存放并计数
//	int ji[10] = { 0 };
//	int J_count = 0;
//	//偶数存放并计数
//	int ou[10] = { 0 };
//	int O_count = 0;
//	//xy分别表示ji和ou的下标
//	int x = 0, y = 0;
//	//j作为arr数组的下标
//	for (int j = 0; j < sz; j++)
//	{
//
//		if (arr[j] % 2 != 0)
//		{
//			ji[y] = arr[j];
//			y++;
//			J_count++;
//		}
//		else
//		{
//			ou[x] = arr[j];
//			x++;
//			O_count++;
//		}
//	}
//	//先把ji数组内的元素赋给arr
//	for (int i = 0; i < J_count; i++)
//	{
//		arr[i] = ji[i];
//	}
//	//承接上述，再把ou数组内的赋给arr后面剩余的空间
//	for (int i = J_count,j=0; i < J_count + O_count; i++,j++)
//	{
//		arr[i] = ou[j];
//	}
//}
//int main()
//{
//	int arr[] = { 1, 2, 4, 3, 5, 6, 7, 8, 9, 10 };
//	int sz = sizeof(arr) / sizeof(arr[0]);
//	swap(arr, sz);
//	for (int i = 0; i < sz; i++)
//	{
//		printf("%d ", arr[i]);
//	}
//	return 0;
//}

////模拟实现库函数strcpy
//#include <assert.h>
//char* My_strcpy(char* arr, const char* brr)
//{
//	assert(arr != NULL);
//	assert(brr != NULL);
//	char* ret = arr;
//	while (*arr++ = *brr++ )
//	{
//		;
//	}
//	return ret;
//}
//int main()
//{
//	char arr[20] = { 0 };
//	char brr[10] = "hello bit";
//	//int sz = sizeof(brr) / sizeof(brr[0]);
//
//	printf("%s", My_strcpy(arr, brr));
//	return 0;
//}




//8月2号作业

////5位运动员参加了10米台跳水比赛，有人让他们预测比赛结果：
////A选手说：B第二，我第三；	我第三	B第二
////B选手说：我第二，E第四；	E第四	我第二
////C选手说：我第一，D第二；	D第二	我第一
////D选手说：C最后，我第三；	C最后	我第三
////E选手说：我第四，A第一；	我第四	我第四
////比赛结束后，每位选手都说对了一半，请编程确定比赛的名次
////1  2  3  4  5
////B  D  A  E  C
////C  B  D  E  A
//int check(char pai[])
//{
//	if (pai[0] + pai[1] + pai[2] + pai[3] + pai[4] == 65 + 66 + 67 + 68 + 69)
//		return 0;
//	else
//		return 1;
//}
//
//void PX(char pai[5], char a, char b, char c, char d, char e)
//{
//	int i = 1;
//	while (i)
//	{
//
//		if (pai[1] = b)
//		{
//			if (pai[1] = b)
//			{
//				if (pai[0] = c)
//				{
//					if (pai[4] = c)
//					{
//						if (pai[3] = e)
//						{
//							i = check(pai);
//							if (i == 0)
//								break;
//						}
//						if (pai[0] = a)
//						{
//							i = check(pai);
//							if (i == 0)
//								break;
//						}
//					}
//					if (pai[2] = d)
//					{
//						if (pai[3] = e)
//						{
//							i = check(pai);
//							if (i == 0)
//								break;
//						}
//						if (pai[0] = a)
//						{
//							i = check(pai);
//							if (i == 0)
//								break;
//						}
//					}
//				}
//				if (pai[1] = d)
//				{
//					if (pai[4] = c)
//					{
//						if (pai[3] = e)
//						{
//							i = check(pai);
//							if (i == 0)
//								break;
//						}
//						if (pai[0] = a)
//						{
//							i = check(pai);
//							if (i == 0)
//								break;
//						}
//					}
//					if (pai[2] = d)
//					{
//						if (pai[3] = e)
//						{
//							i = check(pai);
//							if (i == 0)
//								break;
//						}
//						if (pai[0] = a)
//						{
//							i = check(pai);
//							if (i == 0)
//								break;
//						}
//					}
//				}
//			}
//			if (pai[3] = e)
//			{
//				if (pai[0] = c)
//				{
//					if (pai[4] = c)
//					{
//						if (pai[3] = e)
//						{
//							i = check(pai);
//							if (i == 0)
//								break;
//						}
//						if (pai[0] = a)
//						{
//							i = check(pai);
//							if (i == 0)
//								break;
//						}
//					}
//					if (pai[2] = d)
//					{
//						if (pai[3] = e)
//						{
//							i = check(pai);
//							if (i == 0)
//								break;
//						}
//						if (pai[0] = a)
//						{
//							i = check(pai);
//							if (i == 0)
//								break;
//						}
//					}
//				}
//				if (pai[1] = d)
//				{
//					if (pai[4] = c)
//					{
//						if (pai[3] = e)
//						{
//							i = check(pai);
//							if (i == 0)
//								break;
//						}
//						if (pai[0] = a)
//						{
//							i = check(pai);
//							if (i == 0)
//								break;
//						}
//					}
//					if (pai[2] = d)
//					{
//						if (pai[3] = e)
//						{
//							i = check(pai);
//							if (i == 0)
//								break;
//						}
//						if (pai[0] = a)
//						{
//							i = check(pai);
//							if (i == 0)
//								break;
//						}
//					}
//				}
//			}
//		}
//		if (pai[2] = a)
//		{
//			if (pai[1] = b)
//			{
//				if (pai[0] = c)
//				{
//					if (pai[4] = c)
//					{
//						if (pai[3] = e)
//						{
//							i = check(pai);
//							if (i == 0)
//								break;
//						}
//						if (pai[0] = a)
//						{
//							i = check(pai);
//							if (i == 0)
//								break;
//						}
//					}
//					if (pai[2] = d)
//					{
//						if (pai[3] = e)
//						{
//							i = check(pai);
//						}
//						if (pai[0] = a)
//						{
//							i = check(pai);
//						}
//					}
//				}
//				if (pai[1] = d)
//				{
//					if (pai[4] = c)
//					{
//						if (pai[3] = e)
//						{
//							i = check(pai);
//						}
//						if (pai[0] = a)
//						{
//							i = check(pai);
//						}
//					}
//					if (pai[2] = d)
//					{
//						if (pai[3] = e)
//						{
//							i = check(pai);
//						}
//						if (pai[0] = a)
//						{
//							i = check(pai);
//						}
//					}
//				}
//			}
//			if (pai[3] = e)
//			{
//				if (pai[0] = c)
//				{
//					if (pai[4] = c)
//					{
//						if (pai[3] = e)
//						{
//							i = check(pai);
//						}
//						if (pai[0] = a)
//						{
//							i = check(pai);
//						}
//					}
//					if (pai[2] = d)
//					{
//						if (pai[3] = e)
//						{
//							i = check(pai);
//						}
//						if (pai[0] = a)
//						{
//							i = check(pai);
//						}
//					}
//				}
//				if (pai[1] = d)
//				{
//					if (pai[4] = c)
//					{
//						if (pai[3] = e)
//						{
//							i = check(pai);
//						}
//						if (pai[0] = a)
//						{
//							i = check(pai);
//						}
//					}
//					if (pai[2] = d)
//					{
//						if (pai[3] = e)
//						{
//							i = check(pai);
//						}
//						if (pai[0] = a)
//						{
//							check(pai);
//						}
//					}
//				}
//			}
//		}
//	}
//}
//void PX1(char a, char b, char c, char d, char e)
//{
//	int i = 0;
//	for (i = 0; i < 2; i++)
//	{
//	}
//}
//int main()
//{
//	//char people[5] = { 'A', 'B', 'C', 'D', 'E'};
//
//	char a = 'A';
//	char b = 'B';
//	char c = 'C';
//	char d = 'D';
//	char e = 'E';
//
//	char pai[5] = { '1', '2', '3', '4', '5' };
//	int i = 0;
//	PX(pai, a, b, c, d, e);
//	PX1( a, b, c, d, e);
//	
//	//打印结果
//	for (i = 0; i < 5; i++)
//	{
//		printf("第%d名：%c\n", i + 1, pai[i]);
//	}
//}


//int main()
//{
//	double i = 9;
//	printf("%lf", i);
//}

////更新（上面写错了）
////5位运动员参加了10米台跳水比赛，有人让他们预测比赛结果：
////A选手说：B第二，我第三；
////B选手说：我第二，E第四；
////C选手说：我第一，D第二；
////D选手说：C最后，我第三；
////E选手说：我第四，A第一；
////比赛结束后，每位选手都说对了一半，请编程确定比赛的名次。
//////1  2  3  4  5
//////B  D  A  E  C
//////C  B  D  E  A
//int main()
//{
//	int a, b, c, d, e;
//	for (a = 1; a <= 5; a++)
//	{
//		for (b = 1; b <= 5; b++)
//		{
//			for (c = 1; c <= 5; c++)
//			{
//				for (d = 1; d <= 5; d++)
//				{
//					for (e = 1; e <= 5; e++)
//					{
//						if (((b == 2) + (a == 3)) == 1 && ((b == 2) + (e == 4)) == 1 && ((c == 1) + (d == 2)) == 1 && ((c == 5) + (d == 3)) == 1 && ((e == 4) + (a == 1)) == 1
//							&& a != b&&a != c&&a != d&&a != e&&b != c&&b != d&&b != e&&c != d&&c != e&&d != e)		
//						{
//							printf("A=%d,B=%d,C=%d,D=%d,E=%d\n", a, b, c, d, e);
//						}
//					}
//				}
//			}
//		}
//	}
//	return 0;
//}
//
//
////日本某地发生了一件谋杀案，警察通过排查确定杀人凶手必为4个嫌疑犯的一个。
////以下为4个嫌疑犯的供词 :
////A说：不是我。
////B说：是C。
////C说：是D。
////D说：C在胡说
////已知3个人说了真话，1个人说的是假话。
////现在请根据这些信息，写一个程序来确定到底谁是凶手。
//int main()
//{
//	char kill = 0;
//	for (kill = 'a'; kill <= 'd'; kill++)
//	{
//		if (((kill != 'a') + (kill == 'c') + (kill == 'd') + (kill != 'd')) == 3)
//		{
//			printf("kill=%c", kill);
//		}
//	}
//	return 0;
//}
//
//
////在屏幕上打印杨辉三角。
////	 1
////  1 1
//// 1 2 1
////1 3 3 1
////……
//#define i 10
//#define j 10
//
//int main()
//{
//	//用二维数组进行对上面的数字进行相加
//	int arr[i][j] = { 0 };
//	int x = 0;
//	int y = 0;
//	arr[0][0] = 1;
//	arr[1][0] = 1;
//	arr[1][1] = 1;
//	for (x = 2; x < i; x++)
//	{
//		arr[x][0] = 1;
//		for (y = 1; y < x; y++)
//		{
//			arr[x][y] = arr[x - 1][y - 1] + arr[x - 1][y];
//		}
//		arr[x][x] = 1;
//	}
//
//	//打印
//	for (x = 0; x < i; x++)
//	{
//		for (y = 0; y < j; y++)
//		{
//			if (arr[x][y]!=0)
//			printf("%d ", arr[x][y]);
//		}
//		printf("\n");
//	}
//	return 0;
//}




//8月6号作业

#include <string.h>
//实现一个函数，可以左旋字符串中的k个字符。
//例如：
////ABCD左旋一个字符得到BCDA
////ABCD左旋两个字符得到CDAB
//void reserve(char arr[], int n, int sz)
//{
//	int left = 0;
//	if (n<=sz/2)
//	{
//		while (n)
//		{
//			//先把当前首个字符给存起来
//			char tmp = arr[left];
//			//把除了第一个以外的都向前复制
//			for (int i = 0,j = 1; j<sz; i++, j++ )
//			{
//				arr[i] = arr[j];
//			}
//			//把tmp复制给最后一个
//			arr[sz - 1] = tmp;
//			n--;
//		}
//	}
//	else
//	{
//		printf("输入错误\n");
//	}
//}
//int main()
//{
//	char arr[] = "ABCDE";
//	//printf("%s", arr);
//	int n = 0;
// 	scanf("%d", &n);
//	int sz = strlen(arr);
//	reserve(arr, n, sz);
//	printf("%s", arr);
//	return 0;
//}

//写一个函数，判断一个字符串是否为另外一个字符串旋转之后的字符串。
//例如：给定s1 = AABCD和s2 = BCDAA，返回1
//给定s1 = abcd和s2 = ACBD，返回0.
//AABCD左旋一个字符得到ABCDA
//AABCD左旋两个字符得到BCDAA
//AABCD右旋一个字符得到DAABC

//int reserve(char arr[],char brr[], int n, int sz)
//{
//	int left = 0;
//	int right = sz-1;
//	int i = 0;
//	
//	while (n)
//	{
//		//count用于检测是否全部一样
//		int count = 0;
//		//先把当前首个字符给存起来
//		char tmp = arr[left];
//		//把除了第一个以外的都向前复制
//		for (int i = 0, j = 1; j<sz; i++, j++)
//		{
//			arr[i] = arr[j];
//		}
//		//把tmp复制给最后一个
//		arr[sz - 1] = tmp;
//		n--;
//
//		//每次旋转要检测一次
//		for (i = 0; i <= sz; i++)
//		{
//			if (arr[i] == brr[i])
//			{
//				count++;
//			}
//			if (count == sz + 1)
//			{
//				return 1;
//			}
//		}
//	}
//	return 0;
//}
//int main()
//{
//	char arr[] = "ABCDE";
//	char brr[] = "BCDEA";
//	//printf("%s", arr);
//	int sz = strlen(arr);
//	int n = sz / 2;
//	int ret=reserve(arr,brr, n, sz);
//	printf("%d", ret);
//	return 0;
//}






//9月7号作业

////杨氏矩阵
////有一个数字矩阵，矩阵的每行从左到右是递增的，矩阵从上到下是递增的，请编写程序在这样的矩阵中查找某个数字是否存在。
////要求：时间复杂度小于O(N);
////思路：如果全部遍历一边的话，时间复杂度就是O(N)，题目要求小于O(N)，
//void Yang(int arr[3][3],int a,int col,int row)
//{
//	int i = 0;
//	int j = col-1;
//	while ((i >= 0 && i <= row - 1) && (j >= 0 && j <= col - 1))
//	{
//		if (arr[i][j] < a)
//		{
//			i++;
//		}
//		else if (arr[i][j] > a)
//		{
//			j--;
//		}
//		else
//		{
//			printf("找到了，下标是%d,%d", i, j);
//			return;
//		}
//	}
//	printf("找不到\n");
//	return;
//}
//int main()
//{
//	int arr[3][3] = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
//	int a = 0;
//	printf("请输入要查找的数字:\n");
//	scanf("%d", &a);
//	Yang(arr,a,3,3);
//	return 0;
//}

//练习使用库函数，qsort排序各种类型的数据
////整形
//void print1(int* arr,int sz)
//{
//	for (int i = 0; i < sz; i++)
//	{
//		printf("%d ", arr[i]);
//	}
//	printf("\n");
//}
//int cmp_int(const void* e1, const void* e2)
//{
//	return *(int*)e2 - *(int*)e1;
//}
////结构体
//typedef struct stu
//{
//	char name[20];
//	int age;
//	float tall;
//}Stu;
//void print2(Stu* s, int sz)
//{
//	printf("姓名\t\t年龄\t身高\n");
//	for (int i = 0; i < sz; i++)
//	{
//		printf("%s\t", s[i].name);
//		printf("%d\t", s[i].age);
//		printf("%.2f\t", s[i].tall);
//		printf("\n");
//	}
//}
////用年龄排序
//int cmp_Stu_age(const void*e1,const void*e2)
//{
//	return (*(Stu*)e1).age - (*(Stu*)e2).age;
//}
////用身高排序
//int cmp_Stu_tall(const void*e1, const void* e2)
//{
//	return (*(Stu*)e1).tall - (*(Stu*)e2).tall;
//}
////用姓名首字母排序
//int cmp_Stu_name(const void*e1, const void* e2)
//{
//	return strcmp((*(Stu*)e1).name, (*(Stu*)e2).name);
//}
//int main()
//{
//	//int arr[] = { 9, 5, 8, 7, 4, 6, 3, 1, 2, 0 };
//	//int sz = sizeof(arr) / sizeof(arr[0]);
//	//print1(arr, sz);
//	//qsort(arr,sz,sizeof(arr[0]),cmp_int);
//	//print1(s, sz);
//
//	Stu s[] = { { "zhangsan", 20, 180.6 }, { "lisi     ", 40, 178.5 }, { "wangwu   ", 16, 176 }, {"xiaoming",18,190} };
//	int sz = sizeof(s) / sizeof(s[0]);
//	printf("排序前：\n");
//	print2(s, sz);
//	printf("排序后：\n");
//	qsort(s,sz,sizeof(s[0]),cmp_Stu_name);
//	print2(s, sz);
//
//	return 0;
//}





////9月13号作业
//
////模仿qsort的功能实现一个通用的冒泡排序
//int cmp_int(const void*e1, const void* e2)
//{
//	return *(int*)e1 - *(int*)e2;
//}
//void print(int *arr, int sz)
//{
//	for (int i = 0; i < sz; i++)
//	{
//		printf("%d ", arr[i]);
//	}
//	printf("\n");
//}
//void swap(char* a1,char* a2,size_t size)
//{
//	while (size)
//	{
//		char tmp = *a1;
//		*a1 = *a2;
//		*a2 = tmp;
//		a1++; a2++;
//		size--;
//	}
//}
//void my_qsort(void* arr, size_t num, size_t size, int(*cmp)(const void*, const void*))
//{
//	int i = 0,j = 0;
//	for (i = 0; i < num; i++)
//	{
//		for (j = 0; j < num - 1 - i; j++)
//		{
//			if (cmp_int((char*)arr+(j*size), (char*)arr+((j+1)*size)) > 0)
//			{
//				swap((char*)arr + (j*size), (char*)arr + ((j + 1)*size), size);
//			}
//		}
//	}
//}
//void text1()
//{
//	int arr[] = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
//	int sz = sizeof(arr) / sizeof(arr[0]);
//	print(arr, sz);
//	my_qsort(arr, sz, sizeof(arr[0]), cmp_int);
//	print(arr, sz);
//
//}
//int main()
//{
//	text1();
//	return 0;
//}




//9月15号作业

////模拟实现strlen
//#include<assert.h>
//int my_strlen(const char* arr)
//{
//	assert(arr);
//	int sum = 0;
//	while (*arr)
//	{
//		arr++;
//		sum++;
//	}
//	return sum;
//}
//int main()
//{
//	char arr[] = "abcdef";
//	int ret = my_strlen(arr);
//	printf("%d", ret);
//	return 0;
//}

////模拟实现strcpy
//#include<assert.h>
//char* my_strcpy(char* dest, const char* source)
//{
//	assert(dest&&source);
//	char*ret = dest;
//
//	while(*dest++ = *source++)
//	{
//		;
//	}
//	return ret;
//}
//int main()
//{
//	char arr[] = "xxxxxxxxxxxxxxxxx";
//	char brr[] = "abcdef";
//	printf("%s", my_strcpy(arr, brr));
//	return 0;
//}




//9月17作业

////模拟实现strcmp
//int my_strcmp(char* arr, char* brr)
//{
//	while (*arr == *brr)
//	{
//		if (*arr == '\0'&&*brr == '\0')
//			return 0;
//		arr++; brr++;
//	}
//	return *arr - *brr;
//
//}
//int main()
//{
//	char arr[] = "abc";
//	char brr[] = "abc";
//	int ret=my_strcmp(arr, brr);
//	if (ret > 0)
//	{
//		printf("大于");
//	}
//	else if (ret == 0)
//	{
//		printf("相等");
//	}
//	else
//	{
//		printf("小于");
//	}
//	return 0;
//}

////模拟实现strcat
//#include<assert.h>
//char* my_strcat(char* arr,const char* brr)
//{
//	assert(arr&&brr);
//	char* ret = arr;
//	while (*arr!='\0')
//	{
//		arr++;
//	}
//	while (*brr!='\0')
//	{
//		*arr++ = *brr++;
//	}
//	*arr = '\0';
//	return ret;
//}
//int main()
//{
//	char arr[20] = "abc";
//	char brr[4] = "def";
//	printf("%s",my_strcat(arr,brr));
//}

////模拟实现strstr
//char* my_strstr(const char* arr,const char* brr)
//{
//	char* ret = arr;
//	char* s1 = arr;
//	char* s2 = brr;
//	while (*ret)
//	{
//		s1 = ret;
//		s2 = brr;
//		while (*s1&&*s2&&*s1 == *s2)
//		{
//			s1++; s2++;
//		}
//		if (*s2 == '\0')
//		{
//			return ret;
//		}
//		ret++;
//	}
//	return NULL;
//}
//int main()
//{
//	char arr[] = "chen bo jin";
//	char brr[] = "bo";
//	char* ret = my_strstr(arr, brr);
//	if (ret == NULL)
//	{
//		printf("找不到");
//	}
//	else 
//	printf("%s", ret);
//	return 0;
//}

//int main()
//{
//	char arr[] = "abcdef";
//	char* a = arr;
//	printf("%c\n", *a);
//	a++;
//	printf("%c\n", *a);
//	printf("%s\n", a);
//	return 0;
//}




////9月19号作业
//
////模拟实现memcpy
//#include<assert.h>
//void* my_memcpy(void*arr, void*brr, size_t num)
//{
//	void* ret = arr;
//	assert(arr&&brr);
//	while (num--)
//	{
//		*(char*)arr = *(char*)brr;
//		arr=(char*)arr+1; 
//		brr = (char*)brr+1;
//	}
//	return ret;
//}
//int main()
//{
//	int arr[20] = {0};
//	int brr[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9,10 };
//	int* ret=my_memcpy(brr+2, brr, 20);
//	for (int i = 0; i < 9; i++)
//	{
//		printf("%d ", brr[i]);
//	}
//	return 0;
//}


////模拟实现memmove
//#include<assert.h>
//void* my_memmove(void*dest, void*sorce,size_t num)
//{
//	assert(dest&&sorce);
//	void* ret = dest;
//	//从前往后复制
//	if (dest<sorce)
//	{
//		while (num--)
//		{
//			*(char*)dest = *(char*)sorce;
//			dest = (char*)dest + 1;
//			sorce = (char*)sorce + 1;
//		}
//	}
//	else//从后往前复制
//	{
//		int t=num-1;
//		//先把两个指针指向末尾
//		while (t--)
//		{
//			dest = (char*)dest + 1;
//			sorce = (char*)sorce + 1;
//		}
//		while (num--)
//		{
//			*(char*)dest = *(char*)sorce;
//			dest = (char*)dest - 1;
//			sorce = (char*)sorce - 1;
//		}
//	}
//	return ret;
//}
//int main()
//{
//	int arr[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
//	int* ret=my_memmove(arr+5, arr + 2, 20);
//	for (int i = 0; i < 10; i++)
//	{
//		printf("%d ", arr[i]);
//	}
//	return 0;
//}


////求下列打印的值
//int main()
//{
//	unsigned char puc[4];
//	struct tagPIM
//	{
//		unsigned char ucPim1;
//		unsigned char ucData0 : 1;
//		unsigned char ucData1 : 2;
//		unsigned char ucData2 : 3;
//	}*pstPimData;
//	pstPimData = (struct tagPIM*)puc;
//	memset(puc, 0, 4);
//	pstPimData->ucPim1 = 2;
//	pstPimData->ucData0 = 3;
//	pstPimData->ucData1 = 4;
//	pstPimData->ucData2 = 5;
//	printf("%02x %02x %02x %02x\n", puc[0], puc[1], puc[2], puc[3]);
//	return 0;
//}

//char *GetMemory(void)
//{
//	char p[] = "hello world";
//	return p;
//}
//void Test(void)
//{
//	char *str = NULL;
//	//str = GetMemory();
//	printf(str);
//}
//
//int main()
//{
//	Test();
//	return 0;
//}

//int main()
//{
//	float cen = 0;
//	float inch = 0, foot = 0;
//	scanf("%f", &cen);
//	float m1 = cen* 0.01;
//	float m2 = cen*0.01;
//	inch=m1/= 0.3048 * 12 / 13;
//	foot = m2 /= 0.3048 * 144 / 145;
//	printf("%d %d", (int)foot, (int)inch);
//	return 0;
//}




//9月23号

////找单身狗
////一个数组中只有两个数字是出现一次，其他所有数字都出现了两次。
////编写一个函数找出这两个只出现一次的数字。
////例如：
////有数组的元素是：1，2，3，4，5，1，2，3，4，6
////只有5和6只出现1次，要找出5和6.
//int* Find(int *arr, int sz,int* returnSize)
//{
//	int i = 0;
//	int max = arr[0];
//	//找最大值
//	for (i = 0; i < sz; i++)
//	{
//		if (max < arr[i])
//		{
//			max = arr[i];
//		}
//	}
//	//通过最大值开辟空间
//	int* ceshi = (int*)calloc(sizeof(int)*(max + 1));
//	//通过哈希表找到小于2的数
//	for (i = 0; i < sz; i++)
//	{
//		ceshi[arr[i]]++;
//	}
//	int dan = 0;//只出现一次的元素的个数
//	for (i = 1; i < max + 1; i++)
//	{
//		if (ceshi[i] < 2)
//		{
//			dan++;
//		}
//	}
//	*returnSize = dan;
//	int* ret = (int*)calloc(sizeof(int)*dan);
//	int j = 0;
//	for (i = 1; i < max + 1; i++)
//	{
//		if (ceshi[i] < 2)
//		{
//			ret[j++] = i;
//		}
//	}
//	free(ceshi);
//	ceshi = NULL;
//	return ret;
//}
//int main()
//{
//	int arr[10] = { 1, 2, 3, 4, 5, 1, 2, 3, 4, 6 };
//	int returnSize = 0;
//	int *ret=Find(arr,10,&returnSize);
//	printf("单数的下标为：");
//	for (int i = 0; i < returnSize; i++)
//	{
//		printf("%d ", ret[i]);
//	}
//	printf("\n");
//	return 0;
//}


////模拟实现strncpy
//#include<assert.h>
//char* my_strncpy(char *dest,const char* sorce,int sz)
//{
//	assert(dest&&sorce);
//	char* ret = dest;
//	int i = 0;
//	for (i = 0; i < sz; i++)
//	{
//		dest[i] = sorce[i];
//	}
//	dest[i] = '\0';
//	return ret;
//}
//int main()
//{
//	char arr[20] = "xxxxxxxxxxxxxxxxxxx";
//	char brr[] = "hello word";
//	char* ret=my_strncpy(arr,brr,7);
//	printf("%s", ret);
//	return 0;
//}


////模拟实现strncat
//#include<assert.h>
//char* my_strncat(char* arr,char* brr,int sz)
//{
//	assert(arr&&brr);
//	char* ret = arr;
//	int i = 0;
//	while (arr[i] != '\0')
//	{
//		i++;
//	}
//	int j = 0;
//	while (sz != 0)
//	{
//		arr[i] = brr[j];
//		i++; j++; sz--;
//		if (brr[j] == '\0')
//		{
//			break;
//		}
//	}
//	arr[i] = '\0';
//	return ret;
//}
//int main()
//{
//	char arr[20] = "abc";
//	char brr[] = "def";
//	char* ret=my_strncat(arr, brr, 5);
//	printf("%s", ret);
//	return 0;
//}


////测试atoi
////识别字符中的数字，并且返回数字，第一个字符必须是数字或者空格和+-符号，空格会被排除
//#include<stdlib.h>
//int main()
//{
//	char *arr = "   1  23abc";
//	int i = atoi(arr);
//	printf("%s\n", arr);
//	printf("%d\n", i);
//	return 0;
//}

//int main()
//{
//	int arr[2][5] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
//	printf("%d", **arr);
//	return 0;
//}

////找单身狗1，找到唯一的单独数字
//int Find_1(int* arr,int* x,int sz)
//{
//	int i = 0;
//	int sum = arr[0];
//	for (i = 1; i < sz; i++)
//	{
//		sum = sum^arr[i];
//	}
//	for (i = 0; i < sz; i++)
//	{
//		if (arr[i] == sum)
//		{
//			*x = i;
//			break;
//		}
//	}
//	return sum;
//}
////找单身狗2,，有两个单独的数字
//void Find_2(int arr[],int *x,int* y,int sz)
//{
//	int i = 0;
//	int sum = 0;
//	//全部异或到一起
//	for (i = 0; i < sz; i++)
//	{
//		sum ^= arr[i];
//	}
//
//	//找到sum二进制中为1的1位置
//	int pos = 0;
//	for (i = 0; i < 32; i++)
//	{
//		if ((sum >> i) & 1 == 1)
//		{
//			pos = i;
//		}
//	}
//
//	//进行分组
//	int s1 = 0;
//	int s2 = 0;
//	for (i = 0; i < sz; i++)
//	{
//		if ((arr[i] >> pos) & 1 == 1)
//		{
//			s1 ^= arr[i];
//		}
//		else
//		{
//			s2 ^= arr[i];
//		}
//	}
//	*x = s1;
//	*y = s2;
//}
//int main()
//{
//	int arr[] = { 1, 2, 3, 4, 9, 4, 2, 3, 1, 7 };
//	int sz = sizeof(arr) / sizeof(arr[0]);
//	int x = 0,y=0;
//	//int ret=Find_1(arr,&x,sz);
//	Find_2(arr, &x, &y, sz);
//	printf("出现单数次数的数字分别为：%d %d\n",x,y);
//	return 0;
//}

//int main()
//{
//	//int a = 10, b = 20;
//	//int c = add(a, b);
//	//printf("%d", c);
//	printf("hello word\n");
//	printf("hello ""word\n");
//	return 0;
//}


////模拟实现atoi函数
//#include <ctype.h>
//#include <math.h>
//int Iswell = 0;
//int my_atoi(char *arr, int sz)
//{
//	assert(arr);
//	int flag = 1;
//	//开头空格
//	while (*arr == ' ')
//	{
//		arr++;
//	}
//	//
//	if (*arr == '-')
//	{
//		flag = -1;
//		arr++;
//	}
//	else if (*arr == '+')
//		arr++;
//	int sum = 0;
//	int n = 0;
//
//	while (*arr != '\0')
//	{
//		if (isdigit(*arr))
//		{
//			sum = (*arr - '0')+sum*10;
//			n++;
//			arr++;
//		}
//		else
//			break;
//	}
//	if (*arr == '\0')
//	{
//		Iswell = 1;
//	}
//	return sum;
//}
//int main()
//{
//	char arr[] = "   +123";
//	int sz=strlen(arr);
//	int ret=my_atoi(arr, sz);
//	if (Iswell==1)
//		printf("正常，%d\n", ret);
//	else
//		printf("异常，%d\n", ret);
//
//	return 0;
//}

//
////模拟实现offsetof宏
//#include<stddef.h>
//struct arr
//{
//	char a;
//	int b;
//	char c;
//	double d;
//};
//#define OFFSEROF(type,mem) (size_t)(&((type*)0)->mem)
////解读：先把0转成我们输入的结构体指针类型，
////这时候，我们的成员变量的地址，就会是改成员类型的偏移量
////我们取出此时的地址，强转为size_t类型，就得实现了offsetof宏的效果
//int main()
//{
//	struct arr A1 = {0};
//	//printf("%d\n", offsetof(struct arr,a));
//	//printf("%d\n", offsetof(struct arr, b));
//	//printf("%d\n", offsetof(struct arr, c));
//	//printf("%d\n", offsetof(struct arr, d));
//	printf("%d\n", OFFSEROF(struct arr, a));
//	printf("%d\n", OFFSEROF(struct arr, b));
//	printf("%d\n", OFFSEROF(struct arr, c));
//	printf("%d\n", OFFSEROF(struct arr, d));
//	return 0;
//}


////写一个宏，可以将一个整数的二进制位的奇数位和偶数位交换。
////例子
////11
////00001011	& 01010101(0x55)
////	得到奇数位为1的位置	00000001	然后左移一位
////00001011	& 10101010	
////	得到偶数位为1的位置	00001010	然后右移一位
////二者相加	得到00000111
//#define SWAP(a) ((a&0x55555555)<<1)+((a&0xaaaaaaaa)>>1)
//int main()
//{
//	int a = 10;
//	//11->7
//	printf("%d\n", SWAP(a));
//	return 0;
//}


//N个数求和
//本题的要求很简单，就是求N个数字的和。麻烦的是，这些数字是以有理数分子 / 分母的形式给出的，你输出的和也必须是有理数的形式。
//方法1
//int main()
//{
//	int num = 0;
//	scanf("%d", &num);
//	getchar();
//	int z, m;
//	scanf("%d/%d", &z, &m);
//
//	num--;
//	int sum_z = z;
//	int sum_m = m;
//	while (num)
//	{
//		scanf("%d/%d", &z, &m);
//		int c = 0;
//		if (m<sum_m)
//		{
//			if (sum_m%m == 0)
//			{
//				c = sum_m / m;
//				z *= c;
//			}
//		}
//		else if (m>sum_m)
//		{
//			if (m%sum_m == 0)
//			{
//				c = m / sum_m;
//
//				sum_z *= c;
//				sum_m = m;
//			}
//		}
//		sum_z += z;
//		num--;
//	}
//	//找最后的值的最大公约数
//	int a1 = 0, a2 = sum_z, a3 = sum_m;
//	while (a1 = a2%a3)
//	{
//		a2 = a3;
//		a3 = a1;
//	}
//	sum_m /= a3;
//	sum_z /= a3;
//	if (sum_z>sum_m)
//	{
//		int e = sum_z / sum_m;
//		int f = sum_m%sum_m;
//		printf("%d %d/%d", e, f, sum_m);
//	}
//	else
//	{
//		printf("%d/%d", sum_z, sum_m);
//	}
//	return 0;
//}
////方法2
//int M(int a, int a1)
//{
//	int c, m, n;
//	m = fmax(a, a1);
//	n = fmin(a, a1);
//	while (n != 0)
//	{
//		c = m % n;
//		m = n;
//		n = c;
//	}
//	return m;
//}//辗转相除法，返回最大公因数
//int main(){
//	int n, sum = 0;
//	int a, b;//a表示分子b表示分母
//	scanf("%d", &n);
//	for (int i = 1; i <= n; ++i)
//	{
//		int a1, b1;
//		scanf("%d/%d", &a1, &b1);
//		sum += a1 / b1;
//		a1 = a1 % b1;//提出整数部分
//		if (i == 1)
//		{
//			a = a1, b = b1;//第一次时初始化
//		}
//		else
//		{
//			int m = b * b1 / M(b, b1);
//			//通过最大公因数找到最小公倍数
//			a = a * (m / b) + a1 * (m / b1);
//			b = m;
//			sum += a / b;
//			a = a % b;
//			//通分计算
//		}
//		while (1)
//		{
//			int l = M(a, b);
//			if (l == 1) {
//				break;
//			}
//			a /= l;
//			b /= l;
//		}//while循环约分分子分母使其最简，每次都要操作避免数据溢出
//	}
//	//输出
//	if (sum == 0)
//	{
//		if (a == 0)
//		{
//			printf("0\n");
//		}
//		else
//		{
//			printf("%d/%d", a, b);
//		}
//	}
//	else
//	{
//		printf("%d", sum);
//		if (a == 0)
//		{
//			printf("\n");
//		}
//		else
//		{
//			printf(" %d/%d", a, b);
//		}
//	}
//	return 0;
//}


////英文字母替换加密（大小写转换 + 后移1位）
////本题要求编写程序，将英文字母替换加密。为了防止信息被别人轻易窃取，需要把电码明文通过加密方式变换成为密文。
////变换规则是：将明文中的所有英文字母替换为字母表中的后一个字母，同时将小写字母转换为大写字母，大写字母转换为小写字母。
////例如，字母a->B、b->C、…、z->A、A->b、B->c、…、Z->a。输入一行字符，将其中的英文字母按照以上规则转换后输出，其他字符按原样输出。
//int main()
//{
//	char arr[100];
//	char ch = 0;
//	int i = 0;
//	while ((ch = getchar()) != '\n')
//	{
//		arr[i] = ch;
//
//		i++;
//	}
//	int len = strlen(arr);
//	for (i = 0; i<len; i++)
//	{
//		if (arr[i] >= 'a'&&arr[i] <= 'z')
//		{
//			if (arr[i] == 'z')
//			{
//				arr[i] = 'A';
//				continue;
//			}
//			else
//				arr[i] -= 31;
//		}
//		else if (arr[i] >= 'A'&&arr[i] <= 'Z')
//		{
//			if (arr[i] == 'Z')
//			{
//				arr[i] = 'a';
//				continue;
//			}
//			else
//				arr[i] += 33;
//		}
//	}
//	printf("%s\n", arr);
//	return 0;
//}


////约分最简分式
////分数可以表示为分子 / 分母的形式。编写一个程序，要求用户输入一个分数，然后将其约分为最简分式。
////最简分式是指分子和分母不具有可以约分的成分了。
////如6 / 12可以被约分为1 / 2。当分子大于分母时，不需要表达为整数又分数的形式，即11 / 8还是11 / 8；而当分子分母相等时，仍然表达为1 / 1的分数形式。
//int main()
//{
//	int a, b;
//	scanf("%d/%d", &a, &b);
//	if (a>b)
//	{
//		int c1 = 0;
//		int a2 = a, b2 = b;
//		while (c1 = a2%b2)
//		{
//			a2 = b2;
//			b2 = c1;
//		}
//		a /= b2;
//		b /= b2;
//		printf("%d/%d", a, b);
//	}
//	else if (a == b)
//		printf("1/1");
//	else{
//		int c = 0;
//		int a1 = a, b1 = b;
//		while (c = a1%b1)
//		{
//			a1 = b1;
//			b1 = c;
//		}
//		a /= b1;
//		b /= b1;
//		printf("%d/%d", a, b);
//	}
//	return 0;
//}


//int main()
//{
//	int a, b, c, d, e, gy, f;
//	d = 0;
//	e = 1;
//	scanf("%d", &a);
//	for (int i = 1; i <= a; i++)
//	{
//		scanf("%d/%d", &b, &c);
//		d = d*c;
//		d = d + b*e;
//		e = e*c;
//	}
//	gy = d;
//	if (e < d) gy = e;
//	for (int i = 1; i <= gy; i++)
//	{
//		if (d%i == 0 && e%i == 0) f = i;
//	}
//	if (d%e == 0) printf("%d", d / e);
//	else if (d / e == 0) printf("%d/%d", d, e);
//	else printf("%d %d/%d", d / e, d%e, e);
//	return 0;
//}
//#include<stdio.h>
//#include<math.h>
//#include<stdlib.h>
//int main()
//{
//	double a, c, sum;
//	int b;
//	scanf("%lf", &a);
//	sum = 0;
//	c = 1;
//	b = 1;
//	while (1)
//	{
//		if (c < 0)
//		{
//			c *= -1;
//		}
//		if (c<a)
//			break;
//		if (b % 2 == 0)
//		{
//			c = -1.0 / b;
//			b = b + 3;
//			sum = sum + c;
//		}
//		else if (b % 2 != 0)
//		{
//			c = 1.0 / b;
//			b = b + 3;
//			sum = sum + c;
//		}
//	}
//	printf("sum = %lf", sum);
//	return 0;
//}

//#define PRINTF(n,format) printf("The value "#n" is "format"\n",n);
//int main()
//{
//	int a = 10;
//	PRINTF(a, "%d");
//	return 0;
//}

//////小于m的最大的10个素数
//int main()
//{
//	int m;
//	scanf("%d", &m);
//	int sum = 0;
//	while (m--)
//	{
//		int flag = 0;
//		if (m % 2 == 0)
//			continue;
//		for (int i = 3; i<m / 2; i++)
//		{
//			if (m%i == 0)
//				flag=1;
//		}
//		if (flag == 0)
//		{
//			printf("%6d ", m);
//			sum++;
//		}
//		if (sum == 10)
//		{
//			break;
//		}
//	}
//	return 0;
//}
//
//typedef struct STL
//{
//	int val;
//	struct STL* naxt;
//}SLNode;
////void SLTPopBack(SLNode** pphead)
////{
////	SLNode* tail = *pphead;
////	SLNode* prev = *pphead;
////	while (tail->naxt != NULL)
////	{
////		tail = tail->naxt;
////		if (tail->naxt != NULL)
////		{
////			prev = prev->naxt;
////		}
////	}
////	free(tail);//不能这样，如果只有1个元素时，prev会变成野指针（因为tail和prev指向*pphead），然后对野指针赋值
////	prev->naxt = NULL;
////}
//void SLTPopFront(SLNode** pphead)
//{
//	assert(*pphead);
//	SLNode* prev = *pphead;
//	*pphead = (*pphead)->naxt;
//	free(prev);
//}


////调试
//#include<stdio.h>
//int main()
//{
//	int a, b, c, d, sum = 0, j, k, x, sum1 = 0, f;
//	scanf("%d", &a);
//	for (int i = 1; i <= a; i++)
//	{
//		sum = 0;
//		scanf("%d", &b);
//		f = 0;
//		c = b;
//		while (c)
//		{
//			d = c % 10;
//			c = c / 10;
//			sum = sum + d;
//		}
//		for (j = 2; j <= 9; j++)
//		{
//			k = j*b;
//			sum1 = 0;
//			while (k)
//			{
//				x = k % 10;
//				k = k / 10;
//				sum1 = sum1 + x;
//			}
//			if (sum != sum1)
//			{
//				f = 1;
//				break;
//			}
//		}
//		if (f == 0)
//			printf("%d\n", sum);
//		else
//			printf("NO\n");
//	}
//	return 0;
//}
//
//
////找出不是两个数组共有的元素
////给定两个整型数组，本题要求找出不是两者共有的元素。
//#include<stdio.h>
//int Ishave(int x, int *crr, int max)
//{
//	for (int i = 0; i<max; i++)
//	{
//		if (x == crr[i])
//			return 0;
//	}
//	return 1;
//}
//int main()
//{
//	int arr[21]; int brr[21]; int crr[21];
//	int i = 0;
//	int sum1, sum2;
//	scanf("%d", &sum1);
//	for (i = 0; i<sum1; i++)
//	{
//		scanf("%d", &arr[i]);
//	}
//	getchar();
//	scanf("%d", &sum2);
//	for (i = 0; i<sum2; i++)
//	{
//		scanf("%d", &brr[i]);
//	}
//	int k = 0;
//	for (i = 0; i<sum1; i++)
//	{
//		int flag = 0;
//		for (int j = 0; j<sum2; j++)
//		{
//			if (arr[i] == brr[j])
//			{
//				flag = 1;
//				break;
//			}
//		}
//		if (flag == 0)
//		{
//			if ((Ishave(arr[i], crr, k)))
//			{
//				crr[k++] = arr[i];
//			}
//
//		}
//	}
//
//	for (i = 0; i<sum2; i++)
//	{
//		int flag = 0;
//		for (int j = 0; j<sum1; j++)
//		{
//			if (arr[j] == brr[i])
//			{
//				flag = 1;
//				break;
//			}
//		}
//		if (flag == 0)
//		{
//			if ((Ishave(brr[i], crr, k)))
//			{
//				crr[k++] = brr[i];
//			}
//
//		}
//	}
//
//	for (i = 0; i<k; i++)
//	{
//		if (i != k - 1)
//			printf("%d ", crr[i]);
//		else
//			printf("%d", crr[i]);
//	}
//	return 0;
//}
//
//
////交换最小值和最大值
////本题要求编写程序，先将输入的一系列整数中的最小值与第一个数交换，然后将最大值与最后一个数交换，最后输出交换后的序列。
////注意：题目保证最大和最小值都是唯一的。
//int main()
//{
//	int num, arr[10];
//	scanf("%d", &num);
//	int i;
//	for (i = 0; i<num; i++)
//	{
//		scanf("%d", &arr[i]);
//	}
//	int min = arr[0], x = 0;
//	for (i = 0; i<num; i++)
//	{
//		if (arr[i]<min)
//		{
//			min = arr[i];
//			x = i;
//		}
//	}
//	int tmp = arr[0];
//	arr[0] = min;
//	arr[x] = tmp;
//	int max = arr[0], y = 0;
//	for (i = 0; i<num; i++)
//	{
//		if (arr[i]>max)
//		{
//			max = arr[i];
//			y = i;
//		}
//	}
//	tmp = arr[num - 1];
//	arr[num - 1] = max;
//	arr[y] = tmp;
//	for (i = 0; i<num; i++)
//	{
//		printf("%d ", arr[i]);
//	}
//	return 0;
//}


////7 - 6 数列求和 - 加强版
////给定某数字A（1≤A≤9）以及非负整数N（0≤N≤100000），求数列之和S = A + AA + AAA + ⋯ + AA⋯A（N个A）。例如A = 1, N = 3时，S = 1 + 11 + 111 = 123
//#include<stdio.h>
//int main()
//{
//	int time, num;
//	scanf("%d %d", &num, &time);
//	int ret[100000];
//	if (time == 0)
//	{
//		printf("0");
//		return 0;
//	}
//	int tmp = 0;
//	for (int i = 0; i<time; i++)
//	{
//		ret[i] = (num*(time - i) + tmp) % 10;
//		tmp = (num*(time - i) + tmp) / 10;
//	}
//	if (tmp == 1)
//	{
//		printf("1");
//	}
//	for (int i = time - 1; i >= 0; i--)
//	{
//		printf("%d", ret[i]);
//	}
//	return 0;
//}


////装箱问题
////输入第一行给出物品个数N（≤1000）；第二行给出N个正整数si（1≤si≤100，表示第i项物品的大小）。
////输入样例：
////8
////60 70 80 90 30 40 10 20
////输出样例：
////60 1
////70 2
////80 3
////90 4
////30 1
////40 5
////10 1
////20 2
////5
//int main()
//{
//	int num;
//	scanf("%d", &num);
//	int i = 0;
//	int arr[1000];//存刚开始的数据
//	int box_site[1000];//存每个数据存储的位置
//	int box[1000] = { 0 };//当成箱子
//	for (i = 0; i<num; i++)
//	{
//		scanf("%d", &arr[i]);
//	}
//	//存放数据
//	i = 0;//表示arr的下标，
//	while (i<num)
//	{
//		//找当前数据所能存放的位置，从头开始找
//		int k = 0;//box_site位置的下标
//		while (1)
//		{
//			if (box[k] + arr[i] <= 100)
//			{
//				box[k] += arr[i];
//				box_site[i] = k + 1;
//				i++;
//				break;
//			}
//			else{
//				k++;
//			}
//		}
//	}
//
//	int box_number = 0;//找box_site里最大的数,即需要的箱子数
//	for (i = 0; i<num; i++)
//	{
//		if (box_number<box_site[i])
//		{
//			box_number = box_site[i];
//		}
//	}
//	//打印结果
//	for (int j = 0; j<num; j++)
//	{
//		printf("%d %d\n", arr[j], box_site[j]);
//	}
//	printf("%d", box_number);
//	return 0;
//}


//#include<stdio.h>
//int main()
//{
//	int a[24], i, b;
//	for (i = 0; i<24; i++)
//		scanf("%d", &a[i]);
//	while (scanf("%d", &b))
//	{
//		if (b<0 && b>23)
//			break;
//		else if (a[b]>50)
//			printf("Yes\n");
//		else if (a[b] <= 50)
//			printf("No\n");
//	}
//	return 0;
//}


////7 - 3 查验身份证
//void PrintfBrr(char* brr)
//{
//	for (int i = 0; i<18; i++)
//		printf("%c", brr[i]);
//	printf("\n");
//}
//
//int main()
//{
//	int num;
//	scanf("%d", &num);
//	getchar();
//	int i;
//	char arr[11] = { "10X98765432" };
//	char crr[17] = { '7', '9', ':', '5',
//		'8', '4', '2', '1', '6', '3', '7',
//		'9', ':', '5', '8', '4', '2' };
//	int error = 0;
//	int error_sum = 0;
//	for (i = 0; i<num; i++)
//	{
//		char brr[18];
//		int j = 0;
//		for (j = 0; j<18; j++)
//		{
//			scanf("%c", &brr[j]);
//		}
//		getchar();
//		error = 0;
//		for (j = 0; j<17; j++)
//		{
//			if (brr[j]<'0' || brr[j]>'9')
//			{
//				PrintfBrr(brr);
//				error++;
//				break;
//			}
//		}
//		if (error != 0)
//		{
//			error_sum += error;
//			continue;
//		}
//		int sum = 0;
//		for (j = 0; j<17; j++)
//		{
//			sum += (brr[j] - '0')*(crr[j] - '0');
//		}
//		sum %= 11;
//		if (arr[sum] == brr[17])
//		{
//			continue;
//		}
//		else{
//			error++;
//			error_sum += error;
//			PrintfBrr(brr);
//			continue;
//		}
//	}
//	error_sum += error;
//	if (error_sum == 0)
//		printf("All passed");
//	return 0;
//}
//
//
////试试手气
////我们知道一个骰子有 6 个面，分别刻了 1 到 6 个点。下面给你 6 个骰子的初始状态，即它们朝上一面的点数
////让你一把抓起摇出另一套结果。假设你摇骰子的手段特别精妙，每次摇出的结果都满足以下两个条件：
////1、每个骰子摇出的点数都跟它之前任何一次出现的点数不同；
////2、在满足条件 1 的前提下，每次都能让每个骰子得到可能得到的最大点数。
////那么你应该可以预知自己第 n 次（1≤n≤5）摇出的结果。
//int main()
//{
//	int arr[6];
//	int i = 0;
//	for (i = 0; i<6; i++)
//	{
//		scanf("%d", &arr[i]);
//	}
//	int time;
//	scanf("%d", &time);
//	int brr[6] = { 6, 6, 6, 6, 6, 6 };
//	for (i = 0; i<6; i++)
//	{
//		if (brr[i] == arr[i])
//			brr[i] -= 1;
//	}
//	for (i = 1; i<time; i++)
//	{
//		for (int j = 0; j<6; j++)
//		{
//			brr[j] -= 1;
//			if (brr[j] == arr[j])
//				brr[j] -= 1;
//		}
//	}
//	for (i = 0; i<6; i++)
//	{
//		if (i != 5)
//			printf("%d ", brr[i]);
//		else
//			printf("%d", brr[i]);
//	}
//	return 0;
//}
//
//
////矩阵A乘以B
////给定两个矩阵A和B，要求你计算它们的乘积矩阵AB。需要注意的是，只有规模匹配的矩阵才可以相乘。即若A有Ra​行、Ca​列，B有Rb​行、Cb​列，则只有Ca​与Rb​相等时，两个矩阵才能相乘。
////输入样例1：
////2 3
////1 2 3
////4 5 6
////3 4
////7 8 9 0
////- 1 - 2 - 3 - 4
////5 6 7 8
////输出样例1：
////2 4
////20 22 24 16
////53 58 63 28
//#include<stdio.h>
//int main()
//{
//	int a, b;
//	scanf("%d%d", &a, &b);
//	int arr[a][b], i, j;
//	for (i = 0; i<a; i++)
//	{
//		for (j = 0; j<b; j++)
//		{
//			scanf("%d", &arr[i][j]);
//		}
//	}
//	int c, d;
//	scanf("%d%d", &c, &d);
//	if (b != c)
//	{
//		printf("Error: %d != %d\n", b, c);
//		return 0;
//	}
//	int brr[c][d];
//	for (i = 0; i<c; i++)
//	{
//		for (j = 0; j<d; j++)
//		{
//			scanf("%d", &brr[i][j]);
//		}
//	}
//	printf("%d %d\n", a, d);
//	for (i = 0; i<a; i++)
//	{
//		for (int x = 0; x<d; x++)
//		{
//			int sum = 0;
//			for (j = 0; j<b; j++)
//			{
//				sum += arr[i][j] * brr[j][x];
//			}
//			printf("%d", sum);
//			if (x != d - 1)
//				printf(" ");
//		}
//		printf("\n");
//	}
//	return 0;
//}


////7 - 9 大炮打蚊子
////现在，我们用大炮来打蚊子：蚊子分布在一个M×N格的二维平面上，每只蚊子占据一格。
////向该平面的任意位置发射炮弹，炮弹的杀伤范围如下示意：
//// O
////OXO
//// O
////其中，X为炮弹落点中心，O为紧靠中心的四个有杀伤力的格子范围。
////若蚊子被炮弹命中（位于X格），一击毙命，若仅被杀伤（位于O格），则损失一半的生命力。
////也就是说，一次命中或者两次杀伤均可消灭蚊子。
////现在给出蚊子的分布情况以及连续k发炮弹的落点，给出每炮消灭的蚊子数。
////输入样例 :
////5 6
////00#00#
////000###
////00#000
////000000
////00#000
////2
////1 2
////1 4
////输出样例:
////0
////2
//#include<stdio.h>
//int main()
//{
//	int m, n;
//	scanf("%d%d", &m, &n);
//	getchar();
//	int i, j;
//	char arr[21][21];
//	for (i = 0; i<m; i++)
//	{
//		for (j = 0; j<n; j++)
//		{
//			scanf("%c", &arr[i][j]);
//		}
//		getchar();
//	}
//
//	int num;
//	scanf("%d", &num);
//	int count = 0;
//	for (i = 0; i<num; i++)
//	{
//		int a, b;
//		count = 0;
//		scanf("%d%d", &a, &b);
//		if (arr[a][b] == '#' || arr[a][b] == '*')
//		{
//			arr[a][b] = '0';
//			count++;
//		}
//
//		if (arr[a - 1][b] == '*')
//		{
//			arr[a - 1][b] = '0';
//			count++;
//		}
//		else if (arr[a - 1][b] == '#')
//			arr[a - 1][b] = '*';
//
//		if (arr[a][b - 1] == '*')
//		{
//			arr[a][b - 1] = '0';
//			count++;
//		}
//		else if (arr[a][b - 1] == '#')
//			arr[a][b - 1] = '*';
//
//		if (arr[a][b + 1] == '*')
//		{
//			arr[a][b + 1] = '0';
//			count++;
//		}
//		else if (arr[a][b + 1] == '#')
//			arr[a][b + 1] = '*';
//
//		if (arr[a + 1][b] == '*')
//		{
//			arr[a + 1][b] = '0';
//			count++;
//		}
//		else if (arr[a + 1][b] == '#')
//			arr[a + 1][b] = '*';
//
//		printf("%d\n", count);
//	}
//
//	return 0;
//}


////7 - 7 矩阵运算
////给定一个n×n的方阵，本题要求计算该矩阵除副对角线、最后一列和最后一行以外的所有元素之和。副对角线为从矩阵的右上角至左下角的连线。
////输入样例:
////4
////2 3 4 1
////5 6 1 1
////7 1 8 1
////1 1 1 1
////输出样例 :
////	 35
//int main()
//{
//	int num;
//	scanf("%d", &num);
//	int i = 0, arr[num][num];
//	for (i = 0; i<num; i++)
//	{
//		for (int j = 0; j<num; j++)
//			scanf("%d", &arr[i][j]);
//	}
//	int sum = 0;
//	for (i = 0; i<num; i++)
//	{
//		for (int j = 0; j<num; j++)
//		{
//			if (i != num - 1 && j != num - 1 && (i + j != num - 1))
//				sum += arr[i][j];
//		}
//	}
//	printf("%d", sum);
//	return 0;
//}

////7 - 08 查找指定字符
////输入格式：
////输入的第一行是一个待查找的字符。第二行是一个以回车结束的非空字符串（不超过80个字符）。
////输出格式：
////如果找到，在一行内按照格式“index = 下标”输出该字符在字符串中所对应的最大下标（下标从0开始）；否则输出"Not Found"。
//int main()
//{
//	char a, c;
//	scanf("%c", &a);
//	getchar();
//	char arr[100];
//	int j = 0;
//	while ((c = getchar()) != '\n')
//	{
//		arr[j++] = c;
//	}
//	arr[j] = '\n';
//	for (int i = j - 1; i >= 0; i--)
//	{
//		if (a == arr[i])
//		{
//			printf("index = %d", i);
//			return 0;
//		}
//	}
//	printf("Not Found");
//	return 0;
//}
//
//
////7 - 09 凯撒密码
//#include<stdio.h>
//int main()
//{
//	char arr[80], b;
//	int a, j = 0;
//	while (1)
//	{
//		b = getchar();
//		arr[j++] = b;
//		if (b == '\n')
//			break;
//	}
//	arr[j] = '\n';
//	scanf("%d", &a);
//	while (a <= -26)
//		a += 26;
//	for (int i = 0; i<j; i++)
//	{
//		if (a == 0)
//			break;
//		if ((arr[i] >= 'A'&&arr[i] <= 'Z') ||
//			(arr[i] >= 'a'&&arr[i] <= 'z'))
//		{
//			if ((arr[i] + a >= 'A'&&arr[i] + a <= 'Z') ||
//				(arr[i] + a >= 'a'&&arr[i] + a <= 'z'))
//			{
//				arr[i] += a;
//			}
//			else
//			{
//				int c = a;
//				if (c>0)
//				{
//					while (c--)
//					{
//						if (arr[i] == 'z')
//						{
//							arr[i] = 'a';
//						}
//						else if (arr[i] == 'Z')
//							arr[i] = 'A';
//						else
//							arr[i]++;
//					}
//				}
//				else{
//					while (c++)
//					{
//						if (arr[i] == 'a')
//						{
//							arr[i] = 'z';
//						}
//						else if (arr[i] == 'A')
//							arr[i] = 'Z';
//						else
//							arr[i]--;
//					}
//				}
//			}
//		}
//	}
//	for (int i = 0; i<j; i++)
//	{
//		printf("%c", arr[i]);
//	}
//	return 0;
//}

//typedef struct tree
//{
//	struct tree* left;
//	struct tree* right;
//	int val;
//}TreeNode;
//
//int size = 0;
//int TreeSize(TreeNode* root)
//{
//	if (root == NULL)
//	{
//		return size+0;
//	}
//	else
//	{
//		size++;
//	}
//	TreeSize(root->left);
//	TreeSize(root->right);
//}
//
//int TreeLeafSize(TreeNode* root)
//{
//	return (root->left == NULL) && (root->right == NULL) ? 1 + TreeLeafSize(root->left) + TreeLeafSize(root->right) : 0;
//}
//
//int TreeHeight(TreeNode* root)
//{
//	if (root == NULL)
//	{
//		return 0;
//	}
//}



//void CreateNDate()
//{
//	// 造数据
//	int n = 10000;
//	srand(time(0));
//	const char* file = "data.txt";
//	FILE* fin = fopen(file, "w");
//	if (fin == NULL)
//	{
//		perror("fopen error");
//		return;
//	}
//
//	for (size_t i = 0; i < n; ++i)
//	{
//		int x = rand() % 1000000;
//		fprintf(fin, "%d\n", x);
//	}
//
//	fclose(fin);
//}
//
//void PrintTopK(int k)
//{
//	FILE* fout = fopen("data.txt", "r");
//
//}



//插入排序	时间复杂度：O(N^2)
void Print(int arr[],int sz)
{
	for (int i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}
void InsertSort(int arr[],int sz)
{
	int i;
	int end;
	for (i = 0; i < sz-1; i++)
	{
		end = i;
		while (end >= 0)
		{
			int tmp = arr[end + 1];
			if (tmp < arr[end])
			{
				arr[end + 1] = arr[end];
				arr[end] = tmp;
				end--;
			}
			else
			{
				break;
			}
		}
	}
}
//希尔排序	时间复杂度：大约O（N^1.3）
void XiShell(int arr[], int sz)
{
	int i;
	int gap = sz;
	int end;
	//优化后
	while (gap > 1)
	{
		gap = gap / 3 + 1;// 4  2  1
		for (i = 0; i < sz - gap; i++)
		{
			end = i;
			while (end >= 0)
			{
				int tmp = arr[end + gap];
				if (tmp < arr[end])
				{
					arr[end + gap] = arr[end];
					arr[end] = tmp;
					end -= gap;
				}
				else
				{
					break;
				}
			}
		}
	}

	//优化前
	//for (int j = 0; j < gap; j++)
	//{
	//	for (i = j; i < sz - gap; i+=gap)
	//	{
	//		end = i;
	//		while (end >= 0)
	//		{
	//			int tmp = arr[end + gap];
	//			if (tmp < arr[end])
	//			{
	//				arr[end + gap] = arr[end];
	//				arr[end] = tmp;
	//				end-=gap;
	//			}
	//			else
	//			{
	//				break;
	//			}
	//		}
	//	}
	//}
}

//int main()
//{
//	//int arr[] = { 9, 8, 7, 6, 5, 5, 4, 3, 2, 1, 0, -2 };
//	int arr[] = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
//	int sz = sizeof(arr) / sizeof(arr[0]);
//	Print(arr, sz);
//
//	//InsertSort(arr,sz);
//	XiShell(arr, sz);
//	Print(arr, sz);
//
//	return 0;
//}
//
//
////打印空心的数字金字塔
////输入样例：
////5
////输出样例：
////    1
////   2 2
////  3   3
//// 4     4
////555555555
//void hollowPyramid(int n)
//{
//	int hang = 0;
//	if (n == 1)
//	{
//		printf("1");
//		return;
//	}
//	int c;
//	int Q_kong = n - 1;
//	while (hang<n - 1)
//	{
//		int a = Q_kong;
//		while (a--)
//		{
//			printf(" ");
//		}
//		c = 1 + 2 * hang;
//		while (c)
//		{
//			if (c == 1 || c == 1 + 2 * hang)
//				printf("%d", hang + 1);
//			else
//				printf(" ");
//			c--;
//		}
//		printf("\n");
//		Q_kong--; hang++;
//	}
//	c = 1 + 2 * hang;
//	while (c--)
//		printf("%d", hang + 1);
//	return;
//}
//
//
////使用函数输出指定范围内的Fibonacci数
////其中函数fib须返回第n项Fibonacci数；
////函数PrintFN要在一行中输出给定范围[m, n]内的所有Fibonacci数，
////相邻数字间有一个空格，行末不得有多余空格。如果给定区间内没有Fibonacci数，
////则输出一行“No Fibonacci number”。
////输入样例1：
////20 100 7
////输出样例1：
////fib(7) = 13
////21 34 55 89
//int fib(int n)
//{
//	int a = 1, b = 1;
//	if (n == 1 || n == 2)
//		return 1;
//	int c = a + b;
//	n -= 3;
//	while (n--)
//	{
//		c = c + b;
//		b = a + b;
//		a = b - a;
//	}
//	return c;
//}
//void PrintFN(int m, int n)
//{
//	int a = 1, b = 1;
//	int flag = 0;
//	if (m == 1 && n >= 2)
//	{
//		printf("1 1 2 ");
//		flag++;
//	}
//	else if (m == 1 && n<2)
//	{
//		printf("1 1");
//		flag++;
//	}
//	int c = a + b;
//	while (c <= n)
//	{
//		c = c + b;
//		b = a + b;
//		a = b - a;
//		if (c >= m&&c <= n)
//		{
//			printf("%d", c);
//			flag++;
//			if (c + b <= n)
//				printf(" ");
//		}
//	}
//	if (flag == 0)
//		printf("No Fibonacci number");
//}




//Printf(int* a, int n)
//{
//	for (int i = 0; i < n; i++)
//	{
//		printf("%d ", a[i]);
//	}
//	printf("\n");
//}
//// 直接插入排序
//void InsectSort(int* a, int n)
//{
//	for (int i = 0; i < n - 1; i++)
//	{
//		int end = i;
//		while (end >= 0)
//		{
//			int tmp = a[end + 1];
//			if (a[end]>tmp)
//			{
//				a[end + 1] = a[end];
//				a[end] = tmp;
//				end--;
//			}
//			else
//			{
//				break;
//			}
//		}
//	}
//}
//// 选择排序
//void swap(int* a_now,int* a_new)
//{
//	int tmp = *a_now;
//	*a_now = *a_new;
//	*a_new = tmp;
//}
//void SelectSort(int* a, int n)
//{
//	int left = 0, right = n - 1;
//	for (int i = 0; i < n / 2; i++)
//	{
//		int min = left, max = right;
//		for (int j = left; j <= right; j++)
//		{
//			if (a[min]>a[j])
//			{
//				min = j;
//			}
//			if (a[max] < a[j])
//			{
//				max = j;
//			}
//		}
//		swap(&a[left],&a[min]);
//		if (max == left)
//		{
//			max = min;
//		}
//		swap(a, right, max);
//		left++; right--;
//	}
//}
//// 冒泡排序
//void BubbleSort(int* a, int n)
//{
//	for (int i = 0; i < n;i++)
//	{ 
//		for (int j = 0; j < n - i-1; j++)
//		{
//			if (a[j]>a[j+1])
//			{
//				int tmp = a[j];
//				a[j] = a[j+1];
//				a[j+1] = tmp;
//			}
//		}
//	}
//}
//
//// 快速排序递归实现
//// 快速排序hoare版本
//int PartSort1(int* a, int left, int right);
//// 快速排序挖坑法
//int PartSort2(int* a, int left, int right);
//// 快速排序前后指针法
//int PartSort3(int* a, int left, int right);
//void QuickSort(int* a, int left, int right);
//
//// 快速排序 非递归实现
//void QuickSortNonR(int* a, int left, int right);
//// 堆排序
//void AdjustDwon(int* a, int n, int root)
//{
//
//}
//void HeapSort(int* a, int n)
//{
//
//}
//int main()
//{
//	int arr[] = { 5,4,3,1,2 };
//	int sz = sizeof(arr) / sizeof(arr[0]);
//	Print(arr, sz);
//	SelectSort(arr, sz);
//
//	//BubbleSort(arr,sz);
//	Print(arr, sz);
//
//	return 0;
//}
//
//int PartSort3(int* a, int begin, int end)
//{
//	int keyi = begin;
//	int prev = begin, cur = begin;
//	//while (cur <= end)
//	//{
//	//	while (cur <= end && a[cur] > a[keyi])
//	//	{
//	//		cur++;
//	//	}
//	//	++prev;
//	//	swap(&a[prev], &a[cur]);
//	//	cur++;
//	//}
//	//swap(&a[keyi], &a[prev]);
//
//	while (cur <= end)
//	{
//		if (a[cur] > a[keyi])
//		{
//			cur++;
//		}
//		else
//		{
//			++prev;
//			swap(&a[prev], &a[cur]);
//			cur++;
//		}
//	}
//	swap(&a[keyi], &a[prev]);
//	return prev;
//}
//

//int main()
//{
//	int n;
//	scanf("%d", &n);
//	while (n--)
//	{
//		int a, flag = 0;
//		scanf("%d", &a);
//		for (int i = 2; i <= sqrt(a); i++)
//		{
//			if (a%i == 0)
//			{
//				printf("No\n");
//				flag = 1;
//				break;
//			}
//		}
//		if (flag == 0)
//			printf("Yes\n");
//	}
//}

//#include<math.h>
//#include<stdio.h>
//int Isprime(int n)
//{
//	for (int i = 2; i <= sqrt(n); i++)
//	{
//		if (n%i == 0)
//		{
//			return 0;
//		}
//	}
//	return 1;
//}
//int main()
//{
//	long int n;
//	int i = 2, k = 0;
//	int arr[100];
//	scanf("%ld", &n);
//	while (n!=1)
//	{
//		if (Isprime(i))
//		{
//			if (n%i == 0)
//			{
//				arr[k++] = i;
//				n /= i;
//			}
//			else
//				i++;
//		}
//		else
//			i++;
//	}
//	for (int j = 0; j<k; j++)
//		printf("%d ", arr[j]);
//	return 0;
//}


////7 - 2 素因子分解
//#include<math.h>
//#include<stdio.h>
//int Isprime(int n)
//{
//	for (int i = 2; i <= sqrt(n); i++)
//	{
//		if (n%i == 0)
//		{
//			return 0;
//		}
//	}
//	return 1;
//}
//int main()
//{
//	long num;
//	int arr[100], k = 0;
//	int i = 2;
//	scanf("%ld", &num);
//	printf("%ld=", num);
//	if (num == 1)
//	{
//		printf("1");
//		return 0;
//	}
//	while (num != 1)
//	{
//		if (Isprime(i))
//		{
//			if (num%i == 0)
//			{
//				arr[k++] = i;
//				num /= i;
//			}
//			else
//				i++;
//		}
//		else
//			i++;
//	}
//	int first = arr[0], time = 0;
//	for (int x = 0; x<k; x++)
//	{
//		if (arr[x] == first)
//		{
//			time++;
//		}
//		else
//		{
//			if (time == 1)
//			{
//				printf("%d", first);
//			}
//			else
//			{
//				printf("%d^%d", first, time);
//			}
//			printf("*");
//			first = arr[x];
//			time = 1;
//		}
//	}
//	if (time == 1)
//	{
//		printf("%d", first);
//	}
//	else
//		printf("%d^%d", first, time);
//	return 0;
//}



////6 - 2 统计某类完全平方数
////本题要求实现一个函数，判断任一给定整数N是否满足条件：它是完全平方数，又至少有两位数字相同，如144、676等。
//int IsTheNumber(const int N)
//{
//	if (N <= 0)
//		return 0;
//	//判断是否是完全平方数
//	int a = 1, i = 1;
//	while (a <= N)
//	{
//		a = i*i;
//		if (a == N)
//		{
//			break;
//		}
//		if (a>N)
//			return 0;
//		i++;
//	}
//	//判断是否有相同数字
//	int n = N;
//	int arr[10], j = 0;
//	while (n)
//	{
//		arr[j++] = n % 10;
//		n /= 10;
//	}
//	int flag = 0;
//	for (int k = 0; k<j; k++)
//	{
//		flag = 0;
//		for (int y = k + 1; y<j; y++)
//		{
//			if (arr[k] == arr[y])
//			{
//				flag = 1;
//				break;
//			}
//		}
//		if (flag == 1)
//		{
//			break;
//		}
//	}
//	if (flag == 0)
//		return 0;
//
//	return 1;
//}
//
//
////6 - 3 使用函数求余弦函数的近似值
////本题要求实现一个函数，用下列公式求cos(x)的近似值，精确到最后一项的绝对值小于e：
////cos(x) = x0/ 0!−x2/ 2!+ x4/ 4!−x6/ 6!+ ⋯
//#include<math.h>
//double funcos(double e, double x);
//int main()
//{
//	double e, x;
//
//	scanf("%lf %lf", &e, &x);
//	printf("cos(%.2f) = %.6f\n", x, funcos(e, x));
//
//	return 0;
//}
//double jie(int i)
//{
//	double ret = 1;
//	for (int j = 1; j <= i; j++)
//	{
//		ret *= j;
//	}
//	return ret;
//}
//double funcos(double e, double x)
//{
//	double sum = 1, n=0, m=0, k=1;
//	int i = 2;
//	if (x<0)
//		x *= -1;
//	double flag = -1;
//	while (k >= e)
//	{
//		n = pow(x, i);
//		m = jie(i);
//		k = n / m;
//		sum += flag*k;
//		flag *= -1;
//		i += 2;
//	};
//	return sum;
//}
//
//
////7 - 2 谷歌的招聘
////输入格式：
////输入在第一行给出 2 个正整数，分别是 L（不超过 1000 的正整数，为数字长度）和 K（小于 10 的正整数）。
////接下来一行给出一个长度为 L 的正整数 N。
////
////输出格式：
////在一行中输出 N 中最早出现的 K 位连续数字所组成的素数。
////如果这样的素数不存在，则输出 404。注意，原始数字中的前导零也计算在位数之内。
////例如在 200236 中找 4 位素数，0023 算是解；但第一位 2 不能被当成 0002 输出，因为在原始数字中不存在这个 2 的前导零。
//#include<stdio.h>
//#include<math.h>
////算n的位数
//int number(long int n)
//{
//	int num = 0;
//	while (n)
//	{
//		n /= 10;
//		num++;
//	}
//	return num;
//}
////判断是否为素数
//int Issu(long int n)
//{
//	if (n == 1)
//		return 0;
//	for (int i = 2; i <= sqrt(n); i++)
//	{
//		if (n%i == 0)
//			return 0;
//	}
//	return 1;
//}
////找符合题目的数字
//long int Ishave(int arr[], int l, int k)
//{
//	long int sum = 0;
//	for (int i = 0; i<l - k + 1; i++)
//	{
//		sum = 0;
//		int j = i;
//		int n = k;
//		while (n--)
//		{
//			sum += (arr[j] - '0')*(int)pow(10, n);
//			j++;
//		}
//		if (Issu(sum))
//		{
//			return sum;
//		}
//	}
//	return 0;
//}
//int main()
//{
//	int l, k;
//	int arr[2000];
//	scanf("%d %d", &l, &k);
//	getchar();
//	for (int i = 0; i<l; i++)
//	{
//		char a = getchar();
//		arr[i] = a;
//	}
//
//	long int ret;
//	if (ret = Ishave(arr, l, k))
//	{
//		int k1 = number(ret);
//		if (k1 == k)
//			printf("%d", ret);
//		else{
//			k1 = k - k1;
//			while (k1--)
//			{
//				printf("0");
//			}
//			printf("%d", ret);
//		}
//	}
//	else
//		printf("404");
//	return 0;
//}

//#include<math.h>
//int IsTheNumber(const int N)
//{
//	int b = N;
//	int i = 0, j, k, c = 0, d, x;
//	int a[4];
//	d = (int)sqrt(b);
//	x = d*d;
//	while (b >= 10)
//	{
//		a[i] = b % 10;
//		i++;
//		b = b / 10;
//	}
//	a[i] = b;
//
//	if (x == N)
//	{
//		for (j = 0; j<=i; j++)
//		{
//			c = 0;
//			for (k = 0; k<=i; k++)
//			{
//				if (a[j] == a[k])
//					c++;
//				if (c >= 2)
//					return 1;
//			}
//		}
//	}
//		return 0;
//}
//int main()
//{
//	int a = IsTheNumber(289);
//	return 0;
//}


//7 - 2 校验ISBN - 10编码
//第一种写法，出现段错误
//#include"stdio.h"
//int main()
//{
//	int num;
//	scanf("%d", &num);
//	getchar();
//	int flag = 0;
//	while (num)
//	{
//		char arr[100], ch;
//		int i = 0;
//		while ((ch = getchar()) != '\n')
//		{
//			arr[i] = ch;
//			i++;
//		}
//		arr[i] = '\0';
//		int k = 0;
//		for (int j = 0; j<i - 1; j++)
//		{
//			if (arr[j] == 'X')
//			{
//				for (int j = 0; j<i; j++)
//					printf("%c", arr[j]);
//				printf("\n");
//				num--;
//				flag = 1;
//				k = 1;
//			}
//		}
//		if (k == 1)
//			continue;
//		int sum = 0;
//		for (int j = 0; j<i; j++)
//		{
//			if (arr[j] == 'X')
//			{
//				if (j == i - 1)
//					sum += 100;
//			}
//			else
//				sum = sum + (j + 1)*(arr[j] - '0');
//		}
//		if (sum % 11 != 0)
//		{
//			for (int j = 0; j<i; j++)
//				printf("%c", arr[j]);
//			printf("\n");
//			flag = 1;
//		}
//		num--;
//	}
//	if (flag == 0)
//		printf("All passed\n");
//	return 0;
//}
//////第二种写法
//#include"stdio.h"
//void Print(char arr[][12], int i)
//{
//	for (int j = 0; j<10; j++)
//		printf("%c", arr[i][j]);
//	printf("\n");
//}
//int main()
//{
//	int num;
//	scanf("%d", &num);
//	getchar();
//	char arr[2][12];
//	for (int i = 0; i<num; i++)
//	{
//		int j;
//		for (j = 0; j<10; j++)
//			scanf("%c", &(arr[i][j]));
//		arr[i][j] = '\0';
//		getchar();
//	}
//	int flag = 0;
//	for (int i = 0; i<num; i++)
//	{
//		int sum = 0, k = 0;
//		int j = 0;
//		for (j = 0; j<10; j++)
//		{
//			if (j<9 && arr[i][j] == 'X')
//			{
//				Print(arr, i);
//				flag = 1; k = 1;
//				break;
//			}
//			if (arr[i][j] != 'X')
//				sum += (j + 1)*(arr[i][j] - '0');
//			else
//				sum += 100;
//		}
//		if (k == 1)
//			continue;
//		else
//		{
//			if (sum % 11 != 0)
//			{
//				flag = 1;
//				Print(arr, i);
//			}
//		}
//	}
//	if (flag == 0)
//		printf("All passed\n");
//	return 0;
//}


////7 - 2 字符串转换成十进制整数
////输入一个以#结束的字符串，本题要求滤去所有的非十六进制字符（不分大小写），
////组成一个新的表示十六进制数字的字符串，然后将其转换为十进制数后输出。
////如果在第一个十六进制字符之前存在字符“ - ”，则代表该数是负数。
//#include<stdio.h>
//#include<string.h>
//#include<math.h>
//int main()
//{
//	char arr[1000];
//	char brr[1000];
//	int k = 0;
//	gets(arr);
//	int len = strlen(arr);
//	//存符合的字符
//	for (int i = 0; i<len; i++)
//	{
//		if ((arr[i] >= '0'&&arr[i] <= '9')
//			|| (arr[i] >= 'a'&&arr[i] <= 'f')
//			|| (arr[i] >= 'A'&&arr[i] <= 'F'))
//		{
//			brr[k] = arr[i];
//			k++;
//		}
//	}
//	brr[k] = '\0';
//	//找第一个
//	int c = -1;
//	for (int x = 0; x<len; x++)
//	{
//		if (brr[0]==arr[x])
//		{
//			c = x;
//			break;
//		}
//	}
//	//找符号
//	int flag = 1;
//	while (c >= 0)
//	{
//		if (arr[c] == '-')
//		{
//			flag = -1;
//			break;
//		}
//		if (arr[c] == '+')
//			break;
//		c--;
//	}
//	int sum = 0;
//	for (int i = 0; i<k; i++)
//	{
//		int tmp;
//		if (brr[i] == 'a' || brr[i] == 'A')
//		{
//			tmp = 10;
//		}
//		else if (brr[i] =='b' || brr[i] == 'B')
//		{
//			tmp = 11;
//		}
//		else if (brr[i] == 'c' || brr[i] == 'C')
//		{
//			tmp = 12;
//		}
//		else if (brr[i] == 'd' || brr[i] == 'D')
//		{
//			tmp = 13;
//		}
//		else if (brr[i] == 'e' || brr[i] == 'E')
//		{
//			tmp = 14;
//		}
//		else if (brr[i] == 'f' || brr[i] == 'F')
//		{
//			tmp = 15;
//		}
//		else
//			tmp = brr[i]-'0';
//		sum += tmp*(int)pow(16, k - 1 - i);
//	}
//	sum *= flag;
//	printf("%d", sum);
//	return 0;
//}
//
//
////7 - 4 字符串排序
////输出格式：
////按照以下格式输出排序后的结果：
////
////After sorted :
////每行一个字符串
////输入样例：
////red yellow blue black white
////输出样例：
////After sorted :
////black
////blue
////red
////white
////yellow
//#include<stdio.h>
//#include<string.h>
//void swap(char* brr, char* crr)
//{
//	int len1 = strlen(brr);
//	int len2 = strlen(crr);
//	char crr1[88];
//	strcpy(crr1, crr);
//	int i;
//	for (i = 0; i<len1; i++)
//	{
//		crr[i] = brr[i];
//	}
//	crr[i] = '\0';
//	for (i = 0; i<len2; i++)
//	{
//		brr[i] = crr1[i];
//	}
//	brr[i] = '\0';
//}
//int main()
//{
//	char arr[5][88];
//	for (int i = 0; i<5; i++)
//	{
//		scanf("%s", arr[i]);
//		getchar();
//	}
//	for (int i = 0; i<5; i++)
//	{
//		for (int j = 0; j + 1<5; j++)
//		{
//			if (strcmp(arr[j], arr[j + 1])>0)
//			{
//				swap(arr[j], arr[j + 1]);
//			}
//		}
//	}
//	printf("After sorted:\n");
//	for (int i = 0; i<5; i++)
//	{
//		printf("%s\n", arr[i]);
//	}
//	return 0;
//}
//
//
//
////7 - 5 删除重复字符
////本题要求编写程序，将给定字符串去掉重复的字符后，按照字符ASCII码顺序从小到大排序后输出。
//int Ishave(char ch, char brr[])
//{
//	int len2 = strlen(brr);
//	for (int i = 0; i<len2; i++)
//	{
//		if (ch == brr[i])
//		{
//			return 0;
//		}
//	}
//	return 1;
//}
//int main()
//{
//	char arr[100] = { 0 };
//	char brr[100] = { 0 };
//	gets(arr);
//	int len = strlen(arr);
//	int j = 0;
//	for (int i = 0; i<len; i++)
//	{
//		//没有返回1
//		if (Ishave(arr[i], brr))
//		{
//			brr[j++] = arr[i];
//		}
//	}
//	int len1 = strlen(brr);
//	for (int i = 0; i<len1; i++)
//	{
//		for (int j = 0; j<len1 - 1 - i; j++)
//		{
//			if (brr[j]>brr[j + 1])
//			{
//				char tmp = brr[j];
//				brr[j] = brr[j + 1];
//				brr[j + 1] = tmp;
//			}
//		}
//	}
//	printf("%s\n", brr);
//	return 0;
//}
//
//
////7 - 3 统计一行文本的单词个数
////本题目要求编写程序统计一行字符中单词的个数。所谓“单词”是指连续不含空格的字符串，各单词之间用空格分隔，空格数可以是多个。
//#include<stdio.h>
//#include<string.h>
//int main()
//{
//	char arr[1000] = { 0 };
//	gets(arr);
//	int len = strlen(arr);
//	arr[len] = ' ';
//	len++;
//	int j = 0, k = 1;
//	int sum = 0;
//	while (k<len)
//	{
//		if (arr[j] != ' '&&arr[k] == ' ')
//		{
//			sum++;
//		}
//		j++; k++;
//	}
//	printf("%d", sum);
//}


//#include<stdio.h>
//#include<string.h>
//int main()
//{
//	char s[100];
//	gets(s);
//
//	int len = strlen(s);
//	int i, j, k, c = 0, d = 0, i1 = 0, i2 = 0;
//
//	char m[100] = { 0 }, n[100] = { 0 };
//	for (i = 0; i<len; i++)
//	{
//		c = 0;
//		for (j = 0; j<len; j++)
//		{
//			if (s[i] == s[j])
//				c++;
//		}
//
//		if (c == 1)
//			m[i1++] = s[i];
//		else
//		{
//			for (k = 0; n[k] != '\0'; k++)
//			{
//				if (s[i] == n[k])
//					d++;
//			}
//			if (d == 0)
//			{
//				n[i2++] = s[i];
//				d = 0;
//			}
//		}
//	}
//
//	printf("%s\n", m);
//	printf("%s", n);
//}
//
//
////144.二叉树的前序遍历
//int TreeSize(struct TreeNode* root)
//{
//	if (root == NULL)
//		return 0;
//	return TreeSize(root->left) + TreeSize(root->right) + 1;
//}
//void Addtree(struct TreeNode* root, int* arr, int* i)
//{
//	if (root == NULL)
//		return;
//	arr[(*i)++] = root->val;
//	Addtree(root->left, arr, i);
//	Addtree(root->right, arr, i);
//}
//int* preorderTraversal(struct TreeNode* root, int* returnSize) {
//	struct TreeNode* root1 = root;
//	int len = TreeSize(root1);
//	int* arr = (int*)malloc(sizeof(int)*len);
//	int i = 0;
//	*returnSize = len;
//	Addtree(root, arr, &i);
//	return arr;
//}


//// 选择排序
//void SelectSort(int* a, int n)
//{
//	for (int i = 0; i < n; i++)
//	{
//		int min = a[i];
//		int min_i = i;
//		for (int j = i; j < n; j++)
//		{
//			if (min > a[j])
//			{
//				min = a[j];
//				min_i = j;
//			}
//		}
//		a[min_i] = a[i];
//		a[i] = min;
//	}
//}
//
//
//// 堆排序
//void AdjustDwon(int* a, int n, int root);
//void HeapSort(int* a, int n);
//
//// 冒泡排序
//void BubbleSort(int* a, int n)
//{
//	for (int i = 0; i < n; i++)
//	{
//		for (int j = 0; j < n - i - 1; j++)
//		{
//			if (a[j + 1] > a[j])
//			{
//				int tmp = a[j];
//				a[j] = a[j + 1];
//				a[j + 1] = tmp;
//			}
//		}
//	}
//}
//
//
////PTA 7 - 4 寻找学习之星
////2023级评选学习之星一名，要求：(1) 3门课考试总成绩前两位满足条件（排名第一的优先考虑，排名第二的备选）；(2) 综合评议得分，超过学习之星的小于全体学生的50%。
////若以上两个要求不能同时满足，则无人当选。
////注：(1)为了便于处理，假设没有3门课总成绩同分的情况；(2)学号为位数小于9位的任意整数。
//int main()
//{
//	int num;
//	scanf("%d", &num);
//	int xue[num];
//	int y[num];
//	int s[num];
//	int w[num];
//	int zong[num];
//	for (int i = 0; i<num; i++)
//	{
//		scanf("%d", &xue[i]);
//		scanf("%d", &y[i]);
//		scanf("%d", &s[i]);
//		scanf("%d", &w[i]);
//		scanf("%d", &zong[i]);
//	}
//	int first = 0;
//	int first_i = 0;
//	int second = 0;
//	int second_i = 0;
//	int sum[num];
//	for (int i = 0; i<num; i++)
//	{
//		sum[i] = y[i] + s[i] + w[i];
//	}
//	//first
//	for (int i = 0; i<num; i++)
//	{
//		if (first<sum[i])
//		{
//			first = sum[i];
//			first_i = i;
//		}
//	}
//	sum[first_i] = 0;
//	//second
//	for (int i = 0; i<num; i++)
//	{
//		if (second<sum[i])
//		{
//			second = sum[i];
//			second_i = i;
//		}
//	}
//
//	if (num % 2 == 1)
//	{
//		int chao = 0;
//		for (int i = 0; i<num; i++)
//		{
//			if (zong[i]>zong[first_i])
//				chao++;
//		}
//		if (chao <= num / 2)
//		{
//			printf("The student ID of Learning Star is %d", xue[first_i]);
//			return 0;
//		}
//		chao = 0;
//		for (int i = 0; i<num; i++)
//		{
//			if (zong[i]>zong[second_i])
//				chao++;
//		}
//		if (chao <= num / 2)
//		{
//			printf("The student ID of Learning Star is %d", xue[second_i]);
//			return 0;
//		}
//		printf("No students meet the requirements!");
//		return 0;
//	}
//	else
//	{
//		int chao = 0;
//		for (int i = 0; i<num; i++)
//		{
//			if (zong[i]>zong[first_i])
//				chao++;
//		}
//		if (chao<num / 2)
//		{
//			printf("The student ID of Learning Star is %d", xue[first_i]);
//			return 0;
//		}
//		chao = 0;
//		for (int i = 0; i<num; i++)
//		{
//			if (zong[i]>zong[second_i])
//				chao++;
//		}
//		if (chao<num / 2)
//		{
//			printf("The student ID of Learning Star is %d", xue[second_i]);
//			return 0;
//		}
//		printf("No students meet the requirements!");
//	}
//	return 0;
//}
//




////////////寒假作业
////day1
////求0-n内自守数个数
////自守数是指一个数的平方的尾数等于该数自身的自然数。例如：25 ^ 2 = 625，76 ^ 2 = 5776，9376 ^ 2 = 87909376。请求出n(包括n)以内的自守数的个数
//int main() {
//	int n;
//	scanf("%d", &n);
//	int time = 0;
//	for (int i = 0; i <= n; i++)
//	{
//		int sum = 1;
//		int a = i*i;
//		int b = i;
//		while (b)
//		{
//			b /= 10;
//			sum *= 10;
//		}
//		a %= sum;
//		if (a == i)
//			time++;
//	}
//	printf("%d", time);
//	return 0;
//}
////返回小于 N 的质数个数
//#include<math.h>
//int Isprime(int a)
//{
//	if (a <= 1)
//		return 0;
//	for (int i = 2; i <= sqrt(a); i++)
//	{
//		if (a%i == 0)
//			return 0;
//	}
//	return 1;
//}
//int main() {
//	int a, time = 0;
//	scanf("%d", &a);
//	for (int i = 0; i <= a; i++)
//	{
//		if (Isprime(i))
//			time++;
//	}
//	printf("%d", time);
//	return 0;
//}

//
////二叉树左叶子之和
////优化前
//int IsLeaf(struct TreeNode* root)
//{
//	if (root == NULL)
//		return 0;
//	if (root->left == NULL&&root->right == NULL)
//		return 1;
//	else
//		return 0;
//}
//int sumOfLeftLeaves(struct TreeNode* root) {
//	// write code here
//	if (root == NULL)
//		return 0;
//	int left = sumOfLeftLeaves(root->left);
//	int right = sumOfLeftLeaves(root->right);
//
//	if (IsLeaf(root->left))
//		return left = root->left->val;
//	return left + right;
//}
////优化后
//int sumOfLeftLeaves(struct TreeNode* root) {
//	// write code here
//	if (root == NULL)
//		return 0;
//	int sum = 0;
//
//	if (IsLeaf(root->left))
//		sum = root->left->val;
//	return sum + sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
//}


//day2
// NC31 第一个只出现一次的字符
//在一个长为 字符串中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.（从0开始计数）
//暴力求解，时间复杂度O(N^2)
int FirstNotRepeatingChar(char* str) {
	// write code here
	int len = strlen(str);
	for (int i = 0; i<len; i++)
	{
		int time = 0;
		for (int j = 0; j<len; j++)
		{
			if (str[i] == str[j])
				time++;
		}
		if (time == 1)
			return i;
	}
	return -1;
}
//用哈希表和队列实现，时间复杂度O(N)，空间复杂度O(N)
int FirstNotRepeatingChar(char* str) {
	// write code here
	int len = strlen(str);
	int arr[123] = { 0 };
	int j = -1;
	for (int i = 0; i<len; i++)
	{
		arr[str[i]]++;
	}
	for (int i = 0; i<len; i++)
	{
		if (arr[str[i]] == 1)
			return i;
	}
	return -1;
}

//面试题 01.01.判定字符是否唯一
//实现一个算法，确定一个字符串 s 的所有字符是否全都不同。
//哈希表实现
bool isUnique(char* astr){
	int arr[123] = { 0 };
	int len = strlen(astr);
	for (int i = 0; i<len; i++)
	{
		arr[astr[i]]++;
	}
	for (int i = 0; i<123; i++)
	{
		if (arr[i]>1)
			return false;
	}
	return true;
}
//用位操作符，不借用额外数组实现
bool isUnique(char* astr){
	int num = 0;
	int len = strlen(astr);
	for (int i = 0; i<len; i++)
	{
		int a = astr[i] - 'a';//a存放位移量
		//1左移a位并且与num按位异或
		num = (1 << a) ^ num;
		//如果num被按位异或后的二进制位置的值还是0，则说明重复
		if (((num >> a) & 1 )== 0)
			return false;
	}
	return true;
}
int main()
{
	char arr[10] = "abdcc";
	isUnique(arr);
	return 0;
}


//day3
//面试题 01.02.判定是否互为字符重排
//给定两个由小写字母组成的字符串 s1 和 s2，请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。
bool CheckPermutation(char* s1, char* s2){
	int arr[123] = { 0 }, brr[123] = { 0 };
	int len1 = strlen(s1);
	int len2 = strlen(s2);
	for (int i = 0; i<len1; i++)
	{
		arr[s1[i]]++;
	}
	for (int i = 0; i<len2; i++)
	{
		brr[s2[i]]++;
	}
	for (int i = 0; i<123; i++)
	{
		if (arr[i] != brr[i])
			return false;
	}
	return true;
}
//面试题 01.04.回文排列
//给定一个字符串，编写一个函数判定其是否为某个回文串的排列之一。
//回文串是指正反两个方向都一样的单词或短语。排列是指字母的重新排列。
//回文串不一定是字典当中的单词。
bool canPermutePalindrome(char* s){
	int arr[123] = { 0 };
	int len = strlen(s);
	for (int i = 0; i<len; i++)
	{
		arr[s[i]]++;
	}
	int time = 0;
	for (int i = 0; i<123; i++)
	{
		if (arr[i] % 2 == 1)
			time++;
	}
	if (time>1)
		return false;
	return true;
}


//day4
//OR135 单词缩写
//在日常书面表达中，我们经常会碰到很长的单词，比如"localization"、"internationalization"等。为了书写方便，我们会将太长的单词进行缩写。这里进行如下定义：
//如果一个单词包含的字符个数达到或者超过10则我们认为它是一个长单词。所有的长单词都需要进行缩写，缩写的方法是先写下这个单词的首尾字符，
//然后再在首尾字符中间写上这个单词去掉首尾字符后所包含的字符个数。
//比如"localization"缩写后得到的是"l10n"，"internationalization"缩写后得到的是"i18n"。现给出n个单词，将其中的长单词进行缩写，其余的按原样输出。
#include <stdio.h>
#include<string.h>
int main() {
	int n;
	scanf("%d", &n);
	getchar();
	while (n--)
	{
		char arr[200];
		scanf("%s", arr);
		getchar();
		int len = strlen(arr);
		if (len >= 10)
		{
			printf("%c%d%c\n", arr[0], len - 2, arr[len - 1]);
		}
		else {
			printf("%s\n", arr);
		}
	}
	return 0;
}
//面试题 01.03.URL化
//URL化。编写一种方法，将字符串中的空格全部替换为 % 20。
//假定该字符串尾部有足够的空间存放新增字符，并且知道字符串的“真实”长度。
char* replaceSpaces(char* S, int length){
	int n = 0;
	for (int i = 0; i<length; i++)
	{
		if (S[i] == ' ')
		{
			n++;
		}
	}
	char *arr = malloc(sizeof(char)*(2 * n + length + 1));
	int i = 0, j = 0;
	for (i = 0; i<length;)
	{
		if (S[i] != ' ')
		{
			arr[j++] = S[i++];
		}
		else
		{
			arr[j++] = '%';
			arr[j++] = '2';
			arr[j++] = '0';
			i++;
		}
	}
	arr[j] = '\0';
	return arr;
}


//day5
//面试题 01.06.字符串压缩
//字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。
//比如，字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短，则返回原先的字符串。
//你可以假设字符串中只包含大小写英文字母（a至z）。注意要考虑字符个数大于10的情况
#include<stdlib.h>
//数字转字符串
void TurnS(int t, char* brr)
{
	int sum = t; int n = 0;
	while (sum)
	{
		sum /= 10;
		n++;
	}
	for (int i = n - 1; i >= 0; i--)
	{
		brr[i] = (t % 10) + '0';
		t /= 10;
	}
	brr[n] = '\0';
}
char* compressString(char* S){
	int len1 = strlen(S);
	int time = 1; int time1 = 0;
	int flag = 0;
	//计算大概要消耗多少空间，time为不重复的字符个数
	for (int i = 0; i<len1 - 1; i++)
	{
		if (S[i] != S[i + 1])
		{
			time++;
			time1 = 0;
			flag = 0;
		}
		else
		{
			time1++;
		}
		if (time1 >= 10 && flag == 0)
		{
			time++; flag = 1;
		}
	}
	//开辟空间大一点，以免栈溢出
	char *arr = malloc(sizeof(char)*(2 * len1));
	int i = 0, j = 0, t = 0;
	if (time * 2 >= len1)
		return S;
	else
	{
		arr[j] = S[i];
		while (S[i] != '\0')
		{
			if (S[i] == arr[j])
			{
				t++; i++;
			}
			else
			{
				//考虑是否字符个数是否大于10
				if (t<10)
				{
					j++;
					arr[j] = t + '0';
					j++;
					arr[j] = S[i];
					t = 0;
				}
				else{
					char brr[6];//"10"
					TurnS(t, brr);
					int len2 = strlen(brr);
					for (int c = 0; c<len2; c++)
					{
						j++;
						arr[j] = brr[c];
					}
					j++;
					arr[j] = S[i];
					t = 0;
				}
			}
		}
		//最后一位字符也要考虑是否大于10个
		if (t<10)
		{
			j++;
			arr[j] = t + '0';
		}
		else
		{
			char brr[6];
			TurnS(t, brr);
			int len2 = strlen(brr);
			for (int c = 0; c<len2; c++)
			{
				j++;
				arr[j] = brr[c];
			}
		}
	}
	//最后放个'\0'
	j++;
	arr[j] = '\0';
	return arr;
}
//面试题 05.07.配对交换
//配对交换。编写程序，交换某个整数的奇数位和偶数位，尽量使用较少的指令（也就是说，位0与位1交换，位2与位3交换，以此类推）。
int exchangeBits(int num){
	int j = 0, o = 0;
	for (int i = 0; i<32; i++)
	{
		//奇
		int tmp = 0;
		if (i % 2 == 0)
		{
			if ((num >> i) & 1)
			{
				tmp = (tmp | 1) << i;
			}
			j = j | tmp;
		}
		//偶
		else
		{
			if ((num >> i) & 1)
			{
				tmp = (tmp | 1) << i;
			}
			o = o | tmp;
		}
	}
	o = o >> 1;
	j = j << 1;
	return j | o;
}


//day6
//面试题 08.05.递归乘法
//递归乘法。 写一个递归函数，不使用 * 运算符， 实现两个正整数的相乘。可以使用加号、减号、位移，但要吝啬一些。
int multiply(int A, int B){
	if (B == 0)
		return 0;
	return A + multiply(A, B - 1);
}
//HJ55 挑7
//输出 1到n之间 的与 7 有关数字的个数。
//一个数与7有关是指这个数是 7 的倍数，或者是包含 7 的数字（如 17 ，27 ，37 ... 70 ，71 ，72 ，73...）
#include <stdio.h>
int Ishave7(int n)
{
	while (n)
	{
		if (n % 10 == 7)
			return 1;
		n /= 10;
	}
	return 0;
}
int Ismultiple7(int n)
{
	int sum = 7;
	while (sum <= n)
	{
		if (n == sum)
			return 1;
		sum += 7;
	}
	return 0;
}
int main() {
	int num; int time = 0;
	scanf("%d", &num);
	for (int i = 1; i <= num; i++)
	{
		if (Ishave7(i))
		{
			time++;
		}
		else if (Ismultiple7(i)){
			time++;
		}
		else {
			continue;
		}
	}
	printf("%d", time);
	return 0;
}


//day7
//面试题 16.05.阶乘尾数
//设计一个算法，算出 n 阶乘有多少个尾随零。
int trailingZeroes(int n){
	int time = 0;
	for (long i = 5; i <= n; i += 5)
	{
		int tmp = i;
		while (tmp % 5 == 0)
		{
			time++;
			tmp /= 5;
		}
	}
	return time;
}
//HJ7 取近似值
int main() {
	double a;
	scanf("%lf", &a);
	double b = a + 0.5;
	printf("%d", (int)b);
	return 0;
}




//day8
//OR140 数列
//某种特殊的数列a1, a2, a3, ...的定义如下：a1 = 1, a2 = 2, ..., an = 2 * an − 1 + an - 2 (n > 2)。
//给出任意一个正整数k，求该数列的第k项模以32767的结果是多少？
#include <stdio.h>

int main() {
	int n;
	scanf("%d", &n);
	long arr[32768];
	arr[0] = 1;
	arr[1] = 2;
	for (int i = 2; i<32768; i++)
	{
		arr[i] = (2 * arr[i - 1] + arr[i - 2]) % 32767;
	}
	while (n--)
	{
		int num;
		scanf("%d", &num);
		printf("%ld\n", arr[num - 1]);
	}
	return 0;
}
//HJ40 统计字符
//输入一行字符，分别统计出包含英文字母、空格、数字和其它字符的个数。
//数据范围：输入的字符串长度满足 1≤n≤1000
int main() {
	char arr[2000];
	gets(arr);
	int i = 0; int dig = 0, eng = 0, kong = 0, other = 0;
	while (arr[i] != '\0')
	{
		if (arr[i] >= '0'&&arr[i] <= '9')
			dig++;
		else if (arr[i] >= 'a'&&arr[i] <= 'z' || arr[i] >= 'A'&&arr[i] <= 'Z')
			eng++;
		else if (arr[i] == ' ')
			kong++;
		else
			other++;
		i++;
	}
	printf("%d\n%d\n%d\n%d\n", eng, kong, dig, other);
	return 0;
}


//day9
//1480. 一维数组的动态和
//给你一个数组 nums 。数组「动态和」的计算公式为：runningSum[i] = sum(nums[0]…nums[i]) 。
//请返回 nums 的动态和。
int* runningSum(int* nums, int numsSize, int* returnSize){
	int *arr = (int*)malloc(sizeof(int)*numsSize);
	*returnSize = numsSize; int k = 0;
	for (int i = 0; i<numsSize; i++)
	{
		int tmp = 0;
		for (int j = 0; j <= i; j++)
		{
			tmp += nums[j];
		}
		arr[k++] = tmp;
	}
	return arr;
}
//35. 搜索插入位置
//给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
//请必须使用时间复杂度为 O(log n) 的算法。
//O(N)
int searchInsert(int* nums, int numsSize, int target) {
	for (int i = 0; i<numsSize; i++)
	{
		if (nums[i] == target)
			return i;
		if (nums[i]>target)
			return i;
	}
	return numsSize;
}
//O(log2N)
int searchInsert(int* nums, int numsSize, int target) {
	int left = 0, right = numsSize - 1;
	int mid = (left + right) / 2;
	while (left <= right)
	{
		if (nums[mid]>target)
		{
			right = mid - 1;//中间再-1，因为中间也比较过大小了
			mid = (right + left) / 2;
		}
		else if (nums[mid]<target)
		{
			left = mid + 1;
			mid = (right + left) / 2;
		}
		else
		{
			return mid;
		}
	}
	if (nums[mid]>target)
	{
		//考虑下标为0时的情况
		if (mid == 0)
			return mid;
		else
			return mid - 1;
	}
	else
	{
		return mid + 1;
	}
}



//day10
//33. 搜索旋转排序数组
//整数数组 nums 按升序排列，数组中的值 互不相同 。
//在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，
//使数组变为[nums[k], nums[k + 1], ..., nums[n - 1], nums[0], nums[1], ..., nums[k - 1]]（下标 从 0 开始 计数）。
//例如，[0, 1, 2, 4, 5, 6, 7] 在下标 3 处经旋转后可能变为[4, 5, 6, 7, 0, 1, 2] 。
//给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 - 1 。
//你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
//O(N)
int search(int* nums, int numsSize, int target) {
	for (int i = 0; i<numsSize; i++)
	{
		if (nums[i] == target)
			return i;
	}
	return -1;
}
//1290. 二进制链表转整数
//给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。
//请你返回该链表所表示数字的 十进制值 。
int getDecimalValue(struct ListNode* head) {
	struct ListNode* new = head;
	int num = 0;
	while (new != NULL)
	{
		num++;
		new = new->next;
	}
	int sum = 0;
	for (int i = 1; i <= num; i++)
	{
		sum += head->val*pow(2, num - i);
		head = head->next;
	}

	return sum;
}



//day11
//NC21 链表内指定区间反转
//将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度O(n)，空间复杂度O(1)。
//头插
#include <math.h>
struct ListNode* headInsert(struct ListNode** head, int new_val)
{
	struct ListNode* Node = (struct ListNode*)malloc(sizeof(struct ListNode));
	if (Node == NULL)
		exit(-1);
	Node->val = new_val;
	Node->next = *head;
	*head = Node;
	return *head;
}
struct ListNode* reverseBetween(struct ListNode* head, int m, int n) {
	// write code here
	//先把m-n区域内翻转
	struct ListNode*new = head;
	struct ListNode* arr = NULL;
	int num1 = 1;
	while (new != NULL)
	{
		if (num1 >= m&&num1 <= n)
		{
			headInsert(&arr, new->val);
		}
		num1++;
		new = new->next;
	}
	//把m-n区域内的数据给到head对应的位置
	struct ListNode* ret = head;
	struct ListNode*back = head;
	int num2 = 1;
	while (head&&back)
	{
		back = back->next;
		//特殊情况，只有两个数
		if (m == 1 && num2 == 1)
		{
			head = arr;
			ret = head;
		}

		if (num2 + 1 == m)
		{
			head->next = arr;
		}
		if (num2 == n)
		{
			head->next = back;
		}
		num2++;
		head = head->next;
	}
	return ret;
}

//头插
struct ListNode* headInsert(struct ListNode** head, int new_val)
{
	struct ListNode* Node = (struct ListNode*)malloc(sizeof(struct ListNode));
	if (Node == NULL)
		exit(-1);
	Node->val = new_val;
	Node->next = *head;
	*head = Node;
	return *head;
}
//  //删除节点
//  void DilectNode(struct ListNode** head)
//  {
//     struct ListNode*Next=(*head)->next;
//     if(Next==NULL)

//  }
void headDliect(struct ListNode** head)
{
	struct ListNode* now = *head
		(*head) = (*head)->next;
	free(now);
}

struct ListNode* removeZeroSumSublists(struct ListNode* head) {
	struct ListNode*z = NULL;
	struct ListNode*f = NULL;
	struct ListNode*new = head;
	while (new)
	{
		if ((new->val)>0)
		{
			headInsert(&z, new->val);
		}
		else
		{
			headInsert(&f, new->val);
		}
		new = new->next;
	}
	struct ListNode*z1 = z;

	while (z1 != NULL)
	{
		if (f->val + z->val == 0)
		{
			headDliect(&f);
		}
		z1 = z1->next;
	}
}



//day12
//面试题 02.05.链表求和
//给定两个用链表表示的整数，每个节点包含一个数位。
//这些数位是反向存放的，也就是个位排在链表首部。
//编写函数对这两个整数求和，并用链表形式返回结果。
//被long范围限制
//尾插
void endInsert(struct ListNode** head, int x)
{
	struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
	if (node == NULL)
		exit(-1);
	node->val = x;
	node->next = NULL;
	if ((*head) == NULL)
	{
		(*head) = node; return;
	}
	else
	{
		//不能没有tail当零时变量，因为函数是void型，而且head是传地址调用，如果改变head的位置，函数结束后，外面的位置也会发生变化
		struct ListNode* tail = *head;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = node;
	}
}
//算最大值
int _addTwoNumbers(struct ListNode* head, int i)
{
	if (head == NULL)
		return 0;
	return (head->val)*pow(10, i) + _addTwoNumbers(head->next, i + 1);
}

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){

	if (l1 == NULL&&l2 == NULL)
		return 0;
	if (l1 == NULL || l2 == NULL)
	{
		if (l1 = NULL)
			return l2;
		else
			return l1;
	}
	long int L1 = _addTwoNumbers(l1, 0);
	long int L2 = _addTwoNumbers(l2, 0);

	long int sum = L1 + L2;
	struct ListNode*arr = NULL;
	if (sum == 0)
	{
		struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
		node->val = 0;
		node->next = NULL;
		arr = node;
	}
	while (sum)
	{
		int c = sum % 10;
		//尾插
		endInsert(&arr, c);
		sum /= 10;
	}
	return arr;
}
////////////////////正确写法
//尾插
void endInsert(struct ListNode** head, int x)
{
	struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
	if (node == NULL)
		exit(-1);
	node->val = x;
	node->next = NULL;
	if ((*head) == NULL)
	{
		(*head) = node; return;
	}
	else
	{
		//不能没有tail当零时变量，因为函数是void型，而且head是传地址调用，如果改变head的位置，函数结束后，外面的位置也会发生变化
		struct ListNode* tail = *head;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = node;
	}
}
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
	int tmp = 0;//处理进位
	struct ListNode* arr = NULL;
	while (l1&&l2)
	{
		int sum = l1->val + l2->val + tmp;
		tmp = 0;
		if (sum<10)
		{
			endInsert(&arr, sum);
		}
		else
		{
			sum = sum % 10;
			endInsert(&arr, sum);
			tmp++;
		}
		l1 = l1->next;
		l2 = l2->next;
	}
	while (l1)
	{
		int sum = l1->val + tmp;
		tmp = 0;
		if (sum<10)
		{
			endInsert(&arr, sum);
		}
		else
		{
			sum = sum % 10;
			endInsert(&arr, sum);
			tmp++;
		}
		l1 = l1->next;

	}
	while (l2)
	{
		int sum = l2->val + tmp;
		tmp = 0;
		if (sum<10)
		{
			endInsert(&arr, sum);
		}
		else
		{
			sum = sum % 10;
			endInsert(&arr, sum);
			tmp++;
		}
		l2 = l2->next;
	}
	if (tmp != 0)
	{
		endInsert(&arr, tmp);
	}
	return arr;
}
//1614. 括号的最大嵌套深度
//用栈的思想实现
int maxDepth(char* s) {
	int i = 0;
	int sz = 0;
	int max = 0;
	while (s[i] != '\0')
	{
		if (s[i] == '(')
		{
			sz++;
		}
		if (s[i] == ')')
		{
			sz--;
		}
		max = max<sz ? sz : max;
		i++;
	}
	return max;
}




//day13
//1544. 整理字符串
//一个整理好的字符串中，两个相邻字符 s[i] 和 s[i + 1]，其中 0 <= i <= s.length - 2 ，要满足如下条件:
//若 s[i] 是小写字符，则 s[i + 1] 不可以是相同的大写字符。
//若 s[i] 是大写字符，则 s[i + 1] 不可以是相同的小写字符。
//请你将字符串整理好，每次你都可以从字符串中选出满足上述条件的 两个相邻 字符并删除，直到字符串整理好为止。
//请返回整理好的 字符串 。题目保证在给出的约束条件下，测试样例对应的答案是唯一的。


//LCP 44. 开幕式焰火
//「力扣挑战赛」开幕式开始了，空中绽放了一颗二叉树形的巨型焰火。 
//给定一棵二叉树 root 代表焰火，节点值表示巨型焰火这一位置的颜色种类。请帮小扣计算巨型焰火有多少种不同的颜色
typedef struct stack
{
	int*arr;
	int sz;
}stack;
int Ishave(int val, stack*a)
{
	for (int i = 0; i<a->sz; i++)
	{
		if (val == a->arr[i])
			return 0;
	}
	return 1;
}
void push(int val, stack*a)
{
	a->arr[a->sz] = val;
	a->sz++;
}
void _numColor(struct TreeNode* root, stack* a)
{
	if (root == NULL)
		return;
	if (Ishave(root->val, a))
	{
		push(root->val, a);
	}
	_numColor(root->left, a);
	_numColor(root->right, a);
}
int numColor(struct TreeNode* root){
	stack a;
	a.arr = malloc(sizeof(int) * 1005); a.sz = 0;
	_numColor(root, &a);
	return a.sz;
}


//day14

//563. 二叉树的坡度
//给你一个二叉树的根节点 root ，计算并返回 整个树 的坡度 。
//一个树的 节点的坡度 定义即为，该节点左子树的节点之和和右子树节点之和的 差的绝对值 。如果没有左子树的话，左子树的节点之和为 0 ；没有右子树的话也是一样。空结点的坡度是 0 。
//整个树 的坡度就是其所有节点的坡度之和。
int _findTilt(struct TreeNode* root)
{
	if (root == NULL)
		return 0;
	return _findTilt(root->left) + _findTilt(root->right) + root->val;
}

int findTilt(struct TreeNode* root) {
	if (root == NULL)
		return 0;
	int left = _findTilt(root->left);
	int right = _findTilt(root->right);
	int sum = abs(left - right);
	return findTilt(root->left) + findTilt(root->right) + sum;
}